Module: 前缀函数、Z函数

要解决这个问题，通常的枚举是行不通的，因为它的渐近线是 O(t*s)。因此，对于子串搜索任务，采用了KMP（Knuth-Morris-Pratt）算法。
为了实现这个算法，使用了字符串前缀函数，这是一个长度为n (strong>s)的数字数组，其中每个元素都是 最大长度子字符串 s 的最大自身后缀，匹配其前缀。例如：
 

<正文>
具有 O(n^3) 渐近性的平凡前缀函数算法：


现在我们需要为以下形式的字符串创建一个前缀函数：  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。

 

直线	前缀函数	备注
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

<头> <日># <正文>

输入	输出
1	abababcab 阿布	0 2

Write the program below
#include <iostream> #include <vector> #include <string> using namespace std; vector<int> prefix_function(string s) { int n = (int)s.length(); vector<int> pi(n); for (int i = 0; i < n; ++i) for (int k = 0; k <= i; ++k) if (s.substr(0, k) == s.substr(i - k + 1, k)) pi[i] = k; return pi; } int main() { string s, t; cin >> s >> t; s = t + '#' + s; vector<int> pi; pi = prefix_function(s);
return 0; }