普林斯顿算法讲义（三）(3)

普林斯顿算法讲义（三）(2)https://developer.aliyun.com/article/1484205

游戏规则。

为了清晰和高效，我们的实现是基于 Java String 类表达的。我们简要回顾它们最重要的特性。

• 字符. String 是字符序列。字符的类型是 char，可以有 2¹⁶ 种可能的值。几十年来，程序员们一直关注编码为 7 位 ASCII 或 8 位扩展 ASCII 的字符，但许多现代应用程序需要 16 位 Unicode。
  
• 不可变性. String 对象是不可变的，因此我们可以在赋值语句中使用它们，并且作为方法的参数和返回值，而不必担心它们的值会改变。
  
• 索引. charAt() 方法以常数时间从字符串中提取指定字符。
  
• 长度. length() 方法以常数时间返回字符串的长度。
  
• 子字符串. substring() 方法通常以常数时间提取指定的子字符串。
  警告：从 Oracle 和 OpenJDK Java 7，更新 6 开始，substring() 方法在提取的子字符串大小上需要线性时间和空间。由于我们没有预料到这种 drastical 变化，我们的一些字符串处理代码将受到影响。String API 对其任何方法，包括 substring() 和 charAt()，都不提供性能保证。教训是自行承担风险。
  查看这篇文章获取更多细节。
  
  
• 连接. + 运算符执行字符串连接。我们避免逐个字符附加形成字符串，因为在 Java 中这是一个 二次时间 的过程。（Java 有一个 StringBuilder 类用于这种用途。）
  
• 字符数组. Java 的 String 不是原始类型。标准实现提供了上述操作，以便于客户端编程。相比之下，我们考虑的许多算法可以使用低级表示，比如一个 char 值数组，许多客户端可能更喜欢这种表示，因为它占用更少的空间并且耗时更少。
  

字母表。

一些应用程序涉及从受限字母表中获取的字符串。在这种应用程序中，使用具有以下 API 的 Alphabet.java 类通常是有意义的：

构造函数以 R 个字符的字符串作为参数，该字符串指定了字母表；toChar()和toIndex()方法在常数时间内在字符串字符和介于 0 和 R-1 之间的int值之间进行转换。R()方法返回字母表或基数中的字符数。包括一些预定义的字母表：

Count.java 是一个客户端程序，它在命令行上指定一个字母表，读取该字母表上的一系列字符（忽略不在字母表中的字符），计算每个字符出现的频率，

本章中的 Java 程序。

以下是本章中的 Java 程序列表。单击程序名称以访问 Java 代码；单击参考号以获取简要描述；阅读教科书以获取全面讨论。

Q + A

Q. 什么是 Unicode。

A. Unicode（通用字符编码）= 复杂的 21 位代码，用于表示国际符号和其他字符。

Q. 什么是 UTF-16。

A. UTF-16（Unicode 转换格式）= 复杂的 16 位可变宽度代码，用于表示 Unicode 字符。大多数常见字符使用 16 位（一个char）表示，但代理对使用一对char值表示。如果第一个char值在D800和DFFF之间，则与下一个char（在相同范围内）组合形成代理对。没有 Unicode 字符对应于D800到DFFF。例如，007A表示小写字母 Z，6C34表示中文水的符号，D834 DD1E表示音乐的 G 大调。

Unicode 参考。

Q. 什么是子字符串陷阱？

A. 字符串方法调用s.substring(i, j)返回 s 从索引 i 开始到 j-1 结束的子字符串（而不是在 j 结束，正如你可能会怀疑的那样）。

Q. 如何更改字符串的值？

A. 在 Java 中无法修改字符串，因为字符串是不可变的。如果你想要一个新的字符串，那么你必须使用字符串连接或返回新字符串的字符串方法之一，如toLowerCase()或substring()来创建一个新的字符串。

网页练习

1. **挤压空格。**编写一个程序 Squeeze.java，该程序接受一个字符串作为输入，并删除相邻的空格，最多保留一个空格。
   
2. **删除重复项。**给定一个字符串，创建一个新字符串，其中删除所有连续的重复项。例如，ABBCCCCCBBAB变为ABCBAB。
   
3. **N 个 x 的字符串。**描述以下函数返回的字符串，给定一个正整数N？

public static String mystery(int N) {
   String s = "";
   while(N > 0) {
       if (N % 2 == 1) s = s + s + "x";
       else            s = s + s;
       N = N / 2;
   }
   return s;
}

1. **回文检查。**编写一个函数，该函数以字符串作为输入，并在字符串是回文时返回true，否则返回false。回文是指字符串从前往后读和从后往前读是相同的。
   
2. **Watson-Crick 互补回文检查。**编写一个函数，该函数以字符串作为输入，并在字符串是 Watson-Crick 互补回文时返回true，否则返回false。Watson-Crick 互补回文是指 DNA 字符串等于其反向的互补（A-T，C-G）。
   
3. **Watson-Crick 互补。**编写一个函数，该函数以 A、C、G 和 T 字符的 DNA 字符串作为输入，并返回以其互补替换所有字符的反向字符串。例如，如果输入是 ACGGAT，则返回 ATCCGT。
   
4. **完美洗牌。**给定长度相同的两个字符串s和t，以下递归函数返回什么？

public static String mystery(String s, String t) {
   int N = s.length();
   if (N <= 1) return s + t;
   String a = mystery(s.substring(0, N/2), t.substring(0, N/2));
   String b = mystery(s.substring(N/2, N), t.substring(N/2, N));
   return a + b;
}

1. **二叉树表示。**编写一个名为TreeString.java的数据类型，使用二叉树表示不可变字符串。它应该支持在常数时间内进行连接，并在与字符数成比例的时间内打印出字符串。
   
2. **反转字符串。**编写一个递归函数来反转一个字符串。不要使用任何循环。提示：使用 String 方法substring()。

public static String reverse(String s) {
   int N = s.length();
   if (N <= 1) return s;
   String a = s.substring(0, N/2);
   String b = s.substring(N/2, N);
   return reverse(b) + reverse(a);
}

1. 你的方法效率如何？我们的方法具有线性对数运行时间。
2. **随机字符串。**编写一个递归函数，创建一个由字符’A’和’Z’之间的随机字符组成的字符串。

public static String random(int N) {
   if (N == 0) return "";
   if (N == 1) return 'A' + StdRandom.uniform(26);
   return random(N/2) + random(N - N/2);
}

1. **子序列。**给定两个字符串s和t，编写一个程序 Subsequence.java，确定s是否是t的子序列。也就是说，s的字母应该按照相同的顺序出现在t中，但不一定是连续的。例如accag是taagcccaaccgg的子序列。
   
2. 最长互补回文。 在 DNA 序列分析中，互补回文是一个等于其反向互补的字符串。腺嘌呤（A）和胸腺嘧啶（T）是互补的，胞嘧啶（C）和鸟嘌呤（G）也是互补的。例如，ACGGT 是一个互补回文。这样的序列作为转录结合位点，并与基因扩增和遗传不稳定性相关。给定一个长度为 N 的文本输入，找到文本的最长互补回文子串。例如，如果文本是 GACACGGTTTTA，那么最长的互补回文是 ACGGT。提示：将每个字母视为奇数长度可能回文的中心，然后将每对字母视为偶数长度可能回文的中心。
   
3. DNA 转 RNA。 编写一个函数，该函数接受一个 DNA 字符串（A、C、G、T）并返回相应的 RNA 字符串（A、C、G、U）。
   
4. DNA 互补。 编写一个函数，该函数以 DNA 字符串（A、C、G、T）作为输入，并返回互补的碱基对（T、G、C、A）。DNA 通常以双螺旋结构存在。两条互补的 DNA 链以螺旋结构连接在一起。
   
5. 从十六进制转换为十进制。 Hex2Decimal.java 包含一个函数，该函数接受一个十六进制字符串（使用 A-F 表示数字 11-15）并返回相应的十进制整数。它使用了一些字符串库方法和霍纳方法。

public static int hex2decimal(String s) {
   String digits = "0123456789ABCDEF";  
   s = s.toUpperCase();
   int val = 0;
   for (int i = 0; i < s.length(); i++) {
      char c = s.charAt(i);
      int d = digits.indexOf(c);
      val = 16*val + d;
   }
   return val;
}

1. 替代方案：Integer.parseInt(String s, int radix)。更加健壮，并且适用于负整数。

5.1 字符串排序

原文：algs4.cs.princeton.edu/51radix

译者：飞龙

协议：CC BY-NC-SA 4.0

本节正在大规模施工中。

LSD 基数排序。

程序 LSD.java 实现了用于固定长度字符串的 LSD 基数排序。它包括一种用于对待每个整数作为 4 字节字符串处理的 32 位整数进行排序的方法。当 N 很大时，这种算法比系统排序快 2-3 倍。

MSD 基数排序。

程序 MSD.java 实现了 MSD 基数排序。

三向字符串快速排序。

程序 Quick3string.java 实现了三向字符串快速排序。

问与答

练习

1. 频率计数。 读入一个字符串列表并打印它们的频率计数。算法：将字符串读入数组，使用三向基数快速排序对它们进行排序，并计算它们的频率计数。加速奖励：在三向分区期间计算计数。缺点：使用空间存储所有字符串。备选方案：TST。
   
2. 对均匀分布数据进行排序。 给定 N 个来自 [0, 1] 区间的随机实数，考虑以下算法对它们进行排序：将 [0, 1] 区间分成 N 个等间距子区间。重新排列（类似于累积计数）这 N 个元素，使每个元素都在其适当的桶中。对每个桶中的元素进行插入排序（或者等效地，只对整个文件进行插入排序）。也就是说，对一个级别进行 MSD 基数排序，然后切换到插入排序。[尝试原地进行？] 解决方案：平均总共需要 O(N) 的时间。设 n_i 是桶 i 中的元素数量。插入排序所有桶的预期时间是 O(n)，因为 E[sum_i (n_i)²] <= 2n。
   
3. 给定一个包含 N 个不同长度的十进制整数的数组，描述如何在 O(N + K) 的时间内对它们进行排序，其中 K 是所有 N 个整数的总位数。
   
4. 美国国旗排序。（原地键索引计数）给定一个包含 N 个介于 0 和 R-1 之间的不同值的数组，以线性时间和 O® 的额外空间对它们进行升序排列。导致（本质上）原地字符串排序。
   提示：计算 count[] 数组，告诉你键需要放置的位置。扫描输入数组。取第一个键，找到它应该属于的桶，并将其交换到相应的位置（更新相应的 count[] 条目）。重复第二个键，但要小心跳过已知属于其位置的键。
   

网络练习

1. 2-sum. 给定一个包含 N 个 64 位整数的数组 a[] 和一个目标值 T，确定是否存在两个不同的整数 i 和 j，使得 a[i] + a[j] 等于 T。你的算法应该在最坏情况下线性时间运行。
   解决方案。在线性时间内对数组进行基数排序。从左到右扫描指针 i 和从右到左扫描指针 j：考虑 a[i] + a[j]。如果它大于 T，则推进 j 指针；如果它小于 T，则推进 i 指针；如果它等于 T，则我们找到了所需的索引。
   注意，整数数组可以使用 Franceschini、Muthukrishnan 和 Patrascu 的高级基数排序算法在线性时间和常数额外空间内进行基数排序。
   
2. 在排序的字符串数组中进行二分查找。 实现一个用于排序字符串数组的二分查找版本，它跟踪查询字符串与 lo 和 hi 端点之间已知相同字符的数���。利用这些信息在二分查找过程中避免字符比较。比较此算法与调用 compareTo() 的版本的性能。（compareTo() 方法的优点是它不需要调用 charAt()，因为它是作为 String 数据类型的实例方法实现的。）
   

5.2 查找树

原文：algs4.cs.princeton.edu/52trie

译者：飞龙

协议：CC BY-NC-SA 4.0

本节正在大规模建设中。

具有字符串键的符号表。

可以使用标准符号表实现。而是利用字符串键的附加结构。为字符串（以及其他以数字表示的键）定制搜索算法。目标：像哈希一样快速，比二叉搜索树更灵活。可以有效地支持额外的操作，包括前缀和通配符匹配，例如，IP 路由表希望转发到 128.112.136.12，而实际上转发到 128.112 是它已知的最长匹配前缀。附带好处：快速且占用��间少的字符串搜索。

R 向查找树。 程序 TrieST.java 使用多向查找树实现了一个字符串符号表。

三向查找树。 程序 TST.java 使用三向查找树实现了一个字符串符号表。

参考：快速排序和搜索的算法 作者 Bentley 和 Sedgewick。

属性 A.（Bentley-Sedgewick）给定一个输入集，无论字符串插入的顺序如何，其 TST 中的节点数都是相同的。

证明。在集合中，TST 中每个不同字符串前缀都有一个唯一的节点。节点在 TST 中的相对位置可能会根据插入顺序而改变，但节点数是不变的。

高级操作。

通配符搜索，前缀匹配。R 向查找树和 TST 实现包括用于通配符匹配和前缀匹配的代码。

惰性删除 = 更改单词边界位。急切删除 = 清理任何死亡父链接。

应用：T9 手机文本输入。用户使用手机键盘键入；系统显示所有对应的单词（并在唯一时自动完成）。如果用户键入 0，系统会显示所有可能的自动完成。

问答

练习

1. 编写 R 向查找树字符串集和 TST 的非递归版本。
   
2. 长度为 L 的唯一子字符串。 编写一个程序，从标准输入中读取文本并计算其包含的长度为 L 的唯一子字符串的数量。例如，如果输入是cgcgggcgcg，那么长度为 3 的唯一子字符串有 5 个：cgc、cgg、gcg、ggc和ggg。应用于数据压缩。提示：使用字符串方法substring(i, i + L)提取第 i 个子字符串并插入符号表。另一种解决方案：使用第 i 个子字符串的哈希值计算第 i+1 个子字符串的哈希值。在第一千万位数的π或者第一千万位数的π上测试它。
   
3. 唯一子字符串。 编写一个程序，从标准输入中读取文本并计算任意长度的不同子字符串的数量。（可以使用后缀树非常高效地完成。）
   
4. 文档相似性。 要确定两个文档的相似性，计算每个三字母组（3 个连续字母）的出现次数。如果两个文档的三字母组频率向量的欧几里德距离很小，则它们相似。
   
5. 拼写检查。 编写一个程序 SpellChecker.java，它接受一个包含英语词汇的字典文件的名称，然后从标准输入读取字符串并打印出不在字典中的任何单词。使用一个字符串集。
   
6. 垃圾邮件黑名单。 将已知的垃圾邮件地址插入到存在表中，并用于阻止垃圾邮件。
   
7. 按国家查找 IP。 使用数据文件ip-to-country.csv来确定给定 IP 地址来自哪个国家。数据文件有五个字段（IP 地址范围的开始，IP 地址范围的结束，两个字符的国家代码，三个字符的国家代码和国家名称。请参阅IP-to-country 网站。IP 地址不重叠。这样的数据库工具可用于：信用卡欺诈检测，垃圾邮件过滤，网站上语言的自动选择以及 Web 服务器日志分析。
   
8. Web 的倒排索引。 给定一个网页列表，创建包含网页中包含的单词的符号表。将每个单词与出现该单词的网页列表关联起来。编写一个程序，读取一个网页列表，创建符号表，并通过返回包含该查询单词的网页列表来支持单词查询。
   
9. Web 的倒排索引。 扩展上一个练习，使其支持多词查询。在这种情况下，输出包含每个查询词至少出现一次的网页列表。
   
10. 带有重复项的符号表。
    
11. 密码检查器。 编写一个程序，从命令行读取一个字符串和从标准输入读取一个单词字典，并检查它是否是一个“好”密码。在这里，假设“好”意味着（i）至少有 8 个字符长，（ii）不是字典中的单词，（iii）不是字典中的单词后跟一个数字 0-9（例如，hello5），（iv）不是由一个数字分隔的两个单词（例如，hello2world）。
    
12. 反向密��检查器。 修改上一个问题，使得（ii）-（v）也适用于字典中单词的反向形式（例如，olleh 和 olleh2world）。巧妙的解决方案：将每个单词及其反向形式插入符号表中。
    
13. 随机电话号码。 编写一个程序，接受一个命令行输入 N，并打印 N 个形式为（xxx）xxx-xxxx 的随机电话号码。使用符号表避免多次选择相同的号码。使用这个区号列表来避免打印虚假的区号。使用 R 向 Trie。
    
14. 包含前缀。 向StringSET添加一个方法containsPrefix()，接受字符串 s 作为输入，并在集合中存在包含 s 作为前缀的字符串时返回 true。
    
15. 子字符串匹配。 给定一个（短）字符串列表，您的目标是支持查询，其中用户查找字符串 s，您的任务是报告列表中包含 s 的所有字符串。提示：如果您只想要前缀匹配（字符串必须以 s 开头），请使用文本中描述的 TST。要支持子字符串匹配，请将每个单词的后缀（例如，string，tring，ring，ing，ng，g）插入 TST 中。
    
16. Zipf 定律。 哈佛语言学家乔治·齐普夫观察到，包含 N 个单词的英文文本中第 i 个最常见单词的频率大致与 1/i 成比例，其中比例常数为 1 + 1/2 + 1/3 + … + 1/N。通过从标准输入读取一系列单词，制表它们的频率，并与预测的频率进行比较来测试“齐普夫定律”。
    
17. 打字猴和幂律。（Micahel Mitzenmacher）假设一个打字猴通过将每个 26 个可能的字母以概率 p 附加到当前单词来创建随机单词，并以概率 1 - 26p 完成单词。编写一个程序来估计生成的单词长度的频率分布。如果“abc”被生成多次，则只计算一次。
    
18. 打字猴和幂律。 重复上一个练习，但假设字母 a-z 出现的概率与以下概率成比例，这是英文文本的典型概率。

1. 
   
2. 书的索引。 编写一个程序，从标准输入中读取一个文本文件，并编制一个按字母顺序排列的索引，显示哪些单词出现在哪些行，如下所示的输入。忽略大小写和标点符号。

It was the best of times,
it was the worst of times,
it was the age of wisdom,
it was the age of foolishness,
age 3-4
best 1
foolishness 4
it 1-4
of 1-4
the 1-4
times 1-2
was 1-4
wisdom 4
worst 2

1. 熵。 我们定义一个包含 N 个单词的文本语料库的相对熵为 E = 1 / (N log N) * sum (p[i] log(k) - log(p[i]), i = 1…k)，其中 p_i 是单词 i 出现的次数的比例。编写一个程序，读取一个文本语料库并打印出相对熵。将所有字母转换为小写，并将标点符号视为空格。
   
2. 最长前缀。 真或假。二进制字符串 x 在符号表中的最长前缀要么是 x 的下取整，要么是 x 的上取整（如果 x 在集合中则两者都是）。
   错误。在 { 1, 10, 1011, 1111 } 中，1100 的最长前缀是 1，而不是 1011 或 1111。
   

创意练习

网页练习

5.3 �� 子字符串搜索

原文：algs4.cs.princeton.edu/53substring

译者：飞龙

协议：CC BY-NC-SA 4.0

本节正在大规模施工中。在长字符串中搜索 - 在线。

这个网站是一个关于精确字符串搜索算法的重要资源。

Java 中的高性能模式匹配用于一般字符串搜索，带通配符的搜索和带字符类的搜索。

程序 Brute.java 是暴力字符串搜索。基本上等同于 SystemSearch.java。

拉宾卡普。

程序 RabinKarp.java 实现了拉宾卡普随机指纹算法。

Knuth-Morris-Pratt。

程序 KMP.java 是 Knuth-Morris-Pratt 算法。KMPplus.java 是一个改进版本，时间和空间复杂度与 M + N 成正比（与字母表大小 R 无关）。

Boyer-Moore。

程序 BoyerMoore.java 实现了 Boyer-Moore 算法的坏字符规则部分。它不实现强好后缀规则。

入侵检测系统。

需要非常快速的字符串搜索，因为这些部署在网络的瓶颈处。应用

问答

练习

1. 设计一个从右到左扫描模式的暴力子字符串搜索算法。
   
2. 展示 Brute-Force 算法的跟踪，样式类似于图 XYZ，用于以下模式和文本字符串。

• AAAAAAAB; AAAAAAAAAAAAAAAAAAAAAAAAB
  
• ABABABAB; ABABABABAABABABABAAAAAAAA
  

3. 确定以下模式字符串的 KMP DFA。

• AAAAAAAB
  
• AACAAAB
  
• ABABABAB
  
• ABAABAAABAAAB
  
• ABAABCABAABCB
  

4. 假设模式和文本是在大小为 R >= 2 的字母表上的随机字符串。证明字符比较的期望次数为(N - M + 1) (1 - R^-M) / (1 - R^-1) <= 2 (N - M + 1)。
   
5. 构造一个例子，其中 Boyer-Moore 算法（仅使用坏字符规则）性能较差。
   
6. 如何修改拉宾卡普算法以搜索给定模式，并附加条件中间字符是一个“通配符”（任何文本字符都可以匹配它）。
   
7. 如何修改拉宾卡普算法以确定文本中是否存在 k 个模式子集中的任何一个（比如，所有长度相同）？
   解决方案。 计算 k 个模式的哈希值，并将哈希值存储在一个集合中。
   
8. 如何修改拉宾卡普算法以在 N×N 文本中搜索 M×M 模式？或者在 N×N 文本中搜索其他不规则形状的模式？
   
9. 蒙特卡洛与拉斯维加斯拉宾卡普。
   
10. 在线回文检测。 逐个读入字符。报告每个瞬间当前字符串是否是回文。提示：使用 Karp-Rabin 哈希思想。
    
11. 串联重复。 在字符串 s 中，基本字符串 b 的串联重复是由至少一个连续的基本字符串 b 的副本组成的子字符串。给定 b 和 s，设计一个算法，在 s 中找到 b 的最大长度的串联重复。运行时间应与 M + N 成正比，其中 M 是 b 的长度，N 是 s 的长度。
    解决方案。 这个问题是子字符串搜索的一般化（s 中是否至少有一个连续的 b 的副本？），所以我们需要一个泛化的子字符串搜索算法。创建 k 个 b 的连接副本的 Knuth-Morris-Pratt DFA，其中 k = n/m。现在，在输入 s 上模拟 DFA 并记录它达到的最大状态。从中，我们可以识别最长的串联重复。
    
12. 后缀前缀匹配。 设计一个线性时间算法，找到一个字符串a的最长后缀，恰好匹配另一个字符串b的前缀。
    
13. 循环旋转。 设计一个线性时间算法来确定一个字符串是否是另一个字符串的循环旋转。如果字符串a是字符串b的循环旋转，那么a和b具有相同的长度，a由b的后缀和前缀组成。
    
14. 循环字符串的子串。 设计一个线性时间算法来确定一个字符串 a 是否是循环字符串 b 的子串。
    
15. 最长回文子串。 给定一个字符串 s，找到最长的回文子串（或 Watson-crick 回文串）。解决方案：可以使用后缀树或Manacher’s algorithm在线性时��内解决。这里有一个通常在线性对数时间内运行的更简单的解决方案。首先，我们描述如何在线性时间内找到长度恰好为 L 的所有回文子串：使用 Karp-Rabin 迭代地形成每个长度为 L 的子串（及其反转）的哈希值，并进行比较。由于你不知道 L，重复将你对 L 的猜测加倍，直到你知道最佳长度在 L 和 2L 之间。然后使用二分查找找到确切的长度。
    解决方案。 Manacher.java 是 Manacher 算法的实现。
    
16. 重复子串。 [ Mihai Patrascu] 给定一个整数 K 和长度为 N 的字符串，找到至少出现 K 次的最长子串。
    一个解决方案。 假设你知道重复字符串的长度 L。对长度为 L 的每个子串进行哈希处理，并检查任何哈希是否出现 K 次或更多。如果是，检查以确保你没有运气不佳。由于你不知道 L，重复将你对 L 的猜测加倍，直到你知道最佳长度在 L 和 2L 之间。然后使用二分查找找到正确的值。
    
17. 最长公共子串。 给定两个（或三个）字符串，找到在所有三个字符串中都出现的最长子串。提示：假设你知道最长公共子串的长度 L。对长度为 L 的每个子串进行哈希处理，并检查任何哈希桶是否包含每个字符串的（至少）一个条目。
    
18. 所有匹配。 修改 KMP 以在线性时间内找到所有匹配（而不是最左匹配）。
    
19. 斐波那契字符串。 KMP 的有趣案例。F(1) = B, F(2) = A, F(3) = AB, F(4) = ABA, F(5) = ABAAB, F(N) = F(N-1) F(N-2)。
    
20. 假设 x 和 y 是两个字符串。设计一个线性时间算法来确定是否存在整数 m 和 n 使得 x^m = y^n（其中 x^m 表示 x 的 m 个副本的连接）。
    解决方案。 只需检查 xy = yx 的位置（这个事实并不平凡 - 它来自于 Lyndon-Schutzenberger 定理）。
    
21. 字符串的周期。 让 s 为一个非空字符串。如果对于所有 i = 0, 1, …, N-p-1 都有 s[i] = s[i+p]，则整数 p 被称为 s 的周期。字符串 s 的周期是是 s 的周期中最小的整数 p（可以是 N）。例如，ABCABCABCABCAB 的周期是 3。设计一个线性时间算法来计算字符串的周期。
    
22. 字符串的边界。 给定一个非空字符串 s，如果 s = yw = wz 对于一些字符串 y、z 和 w 且 |y| = |z| = p，则我们将字符串 w 定义为 s 的边界，即 w 是 s 的既是前缀又是后缀的一个合适子串。字符串的边界是 s 的最长合适边界（可以为空）。例如，ABCABCABCABCAB 的边界是 w = ABCABCAB（其中 y = ABC，z = CAB，p = 3）。设计一个线性时间算法来计算字符串的边界。
    
23. 变位词子串搜索。 给定长度为 N 的文本字符串 txt[] 和长度为 M 的模式字符串 pat[]，确定 pat[] 或其任何变位词（其 M! 种排列之一）是否出现在文本中。
    提示：在文本中维护长度为 M 的给定子串的字母频率直方图。
    

5.4 正则表达式

原文：algs4.cs.princeton.edu/54regexp

译者：飞龙

协议：CC BY-NC-SA 4.0

本节正在大力整理中。

正则表达式。

NFA.java, DFS.java, Digraph.java, 和 GREP.java.

运行时间。

M = 表达式长度，N = 输入长度。正则表达式匹配算法可以在 O(M)时间内创建 NFA，并在 O(MN)时间内模拟输入。

库实现。

Validate.java。

大多数正则表达式库实现使用回溯算法，在某些输入上可能需要指数级的时间。这样的输入可能非常简单。例如，确定长度为 N 的字符串是否与正则表达式(a|aa)*b匹配，如果选择字符串得当，可能需要指数级的时间。下表展示了 Java 1.4.2 正则表达式的失败情况。

java Validate "(a|aa)*b" aaaaaaaaaaaaaaaaaaaaaaaaaaaaaac             1.6 seconds
java Validate "(a|aa)*b" aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac           3.7 seconds
java Validate "(a|aa)*b" aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac         9.7 seconds
java Validate "(a|aa)*b" aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac      23.2 seconds
java Validate "(a|aa)*b" aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac    62.2 seconds
java Validate "(a|aa)*b" aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac 161.6 seconds

java Validate "(a*)*|b*" aaaaaaaaaaaaaaaaaaaaac           1.28
java Validate "(a*)*|b*" aaaaaaaaaaaaaaaaaaaaaac          2.45
java Validate "(a*)*|b*" aaaaaaaaaaaaaaaaaaaaaaac         4.54
java Validate "(a*)*|b*" aaaaaaaaaaaaaaaaaaaaaaaac        8.84
java Validate "(a*)*|b*" aaaaaaaaaaaaaaaaaaaaaaaaac      17.74
java Validate "(a*)*|b*" aaaaaaaaaaaaaaaaaaaaaaaaaac     33.77
java Validate "(a*)*|b*" aaaaaaaaaaaaaaaaaaaaaaaaaaac    67.72
java Validate "(a*)*|b*" aaaaaaaaaaaaaaaaaaaaaaaaaaaac  134.73

普林斯顿算法讲义（三）（4)https://developer.aliyun.com/article/1484212