带你读《图解算法小抄》二十四、字符串（4）https://developer.aliyun.com/article/1347815?groupCode=tech_library
5.Z 算法
Z 算法用于在线性时间 O(|W| + |T|) 内查找主字符串 T 中的一个单词 W 的出现位置。
给定长度为 n 的字符串 S，该算法产生一个数组 Z，其中 Z[i] 表示以 S[i] 开头的最长子串，该子串也是 S 的前缀。通过计算在单词 W 后连接一个特殊字符（例如 $）和文本 T 后所得到的字符串的 Z 数组，可以帮助进行模式匹配。如果存在某个索引 i，使得 Z[i] 等于模式的长度，则该模式必定存在于该位置。
尽管可以使用两层嵌套循环以 O(|W| * |T|) 的时间计算 Z 数组，但下面的策略展示了如何在线性时间内获得 Z 数组。其基本思想是，当我们迭代字符串中的字母时（索引从 1 到 n-1），我们维护一个区间 [L, R]，它是具有最大 R 的区间，使得 1 ≤ L ≤ i ≤ R 且 S[L...R] 是一个同时是前缀和子串的字符串（如果不存在这样的区间，则令 L = R = -1）。对于 i = 1，我们可以通过比较 S[0...] 和 S[1...] 来计算 L 和 R。
1）Z 数组示例
Index 0 1 2 3 4 5 6 7 8 9 10 11 Text a a b c a a b x a a a z Z values X 1 0 0 3 1 0 0 2 2 1 0
其他示例
str = a a a a a a Z[] = x 5 4 3 2 1
str = a a b a a c d Z[] = x 1 0 2 1 0 0
str = a b a b a b a b Z[] = x 0 6 0 4 0 2 0
2）复杂度
- 时间复杂度：O(|W| + |T|)
- 空间复杂度：O(|W|)
3）参考资料
- GeeksForGeeks
- YouTube
- Ivan Yurchenko 的 Z 算法文章
6.Knuth–Morris–Pratt 算法
Knuth–Morris–Pratt 字符串搜索算法（或 KMP 算法）通过利用以下观察结果，在主文本字符串 T 中搜索单词 W 的出现。当出现不匹配时，单词本身提供了足够的信息来确定下一次匹配可以开始的位置，从而避免重新检查先前匹配的字符。
1）复杂度
- 时间复杂度： O(|W| + |T|)（比朴素算法 O(|W| * |T|) 更快）
- 空间复杂度： O(|W|)
2）参考资料
- 维基百科
- YouTube
带你读《图解算法小抄》二十四、字符串（6）https://developer.aliyun.com/article/1347812
