要解决这个问题，通常的枚举是行不通的，因为它的渐近线是
O(t*s)。因此，对于子串搜索任务，采用了KMP（Knuth-Morris-Pratt）算法。
为了实现这个算法，使用了字符串前缀函数，这是一个长度为
n (strong>s)的数字数组，其中每个元素都是 最大长度子字符串
s 的最大自身后缀，匹配其前缀。例如：
<正文>
| 直线 |
前缀函数 |
备注 |
| abababcab |
0 0 1 2 3 4 0 1 2 |
|
| abcabcd |
0 0 0 1 2 3 0 |
|
| 啊啊啊啊 |
0 1 0 1 2 2 3 |
|
具有 O(n^3) 渐近性的平凡前缀函数算法：
矢量<int> prefix_function（字符串 s）{
int n = (int ) s.长度();
矢量<int>pi(n);
对于 (int i=0; i<n; ++i)
对于 (int k=0; k<=i; ++k)
如果 (s.substr(0,k) == s .substr(i-k+1,k))
pi[i] = k;
返回pi;
}
现在我们需要为以下形式的字符串创建一个前缀函数： t + # + s，其中#是一个明显不在文本中的分隔符。 分析相应分隔符后的前缀函数的值，需要注意的是，如果结果值等于想要的子串的长度，那么就找到了它的出现。例如，对于字符串“abababcab”和所需的子字符串“abab”，前缀函数将是：
0 0 1 2 0 1 2 3 4 3 4 0 1 2我们需要解析对应字符串s的元素：
1 2 3 4 3 4 0 1 2 - 在两种情况下值为 4（第 4 和第 6），即长度t, 结果，答案必须写成：4 - 4（长度t） = 0 和 6 - 4 = 2。可以看出这些是正确的答案，字符串“abab”是正确的。实际上是字符串“abababcab”中的一个子串在位置 0 和 2。
优化前缀函数后（详情请点击 此处），我们得到具有 O(n) 渐近性的最终算法：
矢量<int> prefix_function（字符串 s）{
int n = (int ) s.长度();
矢量<int>pi(n);
对于 (int i=1; i<n; ++i) {
int j = pi[i-1< /跨度>];
同时 (j > 0 && s[i] != s[j])
j = pi[j-1];
如果 (s[i] == s[j]) ++j；
pi[i] = j;
}
返回pi;
}
|
Z-函数
Z-function from string S - 数组Z，其中每个元素都是Z [i ]等于字符串S中从位置i开始的子串的最长前缀，也是整个字符串的前缀>Z。 Z 函数在位置零处的值通常为零或整个字符串的长度。
难度
O(|S| ^ 2) 或O(|S|)。
前缀函数来自字符串 S - 数组 P，其中 P[i]的每个元素等于最长的后缀字符串 S中位置 i开始的子串，也是整个字符串 S的后缀。 P-function 在位置零处的值通常为零或整个字符串的长度。
难度
O(|S| ^ 2) 或O(|S|)。
尝试实现Z函数和prefix函数 for O(|S| ^ 2) .
|
Z 和函数前缀均可用于实现 KMP(Knuth-Morris-Pratt) 算法，用于在 O(|S|) 的字符串中查找子字符串。该算法的本质如下：我们将要查找的字符串归因于我们要查找的字符串。非常希望在这些行之间放置一个分隔符，即一个不出现在任何行中的字符（通常是#）。
|