Z函数（扩展KMP）
用于解决以下问题：给定一个长度为n的字符串\(s\)，求出一个数组\(z\)，其中\(z_i\)表示字符串\(s(0, n - 1)\)和\(s(i, n - 1)\)的最长公共前缀。其中 \(|s| <= 2 \times 10^7\)。
假设当前已经求出了\(z_0\)到\(z_{i - 1}\)，下一个要求\(z_i\)：
设\(p\)为\(1\)到\(i - 1\)中，能匹配到的最远距离，即：\(p = max(j + z_j - 1), j \in [1, i - 1]\)，记\(p\)取最大值时\(j\)的值为\(k\).
可知:字符串\(s(0, z_k - 1)\)和\(s(k, k + z_k - 1)\)是相等的.
假设此时要求的\(i \in [k, k + z_k - 1]\),可知\(s(i, k + z_k - 1)\)和\(s(i - k, z_k - 1)\)是相等的。
记\(l = z_{i - k}\), 则\(s(0, l - 1)\)和\(s(i - k, i - k + l - 1)\)是相等的. 又因为\(s(i - k, i - k + l - 1)\)和\(s(i, i + l - 1)\)是相等的,因此我们找到了从\(i\)开始的一段长为\(l\)的公共前缀.下面分两种情况:
1.当\(i + l - 1 \leq p\)时,\(z_{i}\)的值即为\(l\).
2.当\(i + l - 1 \geq p\)时,大于\(p\)的部分不一定能和前面匹配上,因此应该从\(p\)开始往后扩展.
算法的复杂度为\(O(n)\),\(n\)为字符串的长度.
代码
const int N = 20000005;
int n, z[N];
string s;
void Z(string &s) {
n = s.size();
int p = 0, k = 1; z[0] = n;
while(z[1] + 1 < n && (s[z[1] + 1] == s[z[1]])) z[1]++;
p = z[1]; k = 1;
for(int i = 2; i < n; i++) {
int l = z[i - k];
if(i + l - 1 <= p) {
z[i] = l;
} else {
z[i] = max(0, p - i + 1);
while(z[i] + i < n && (s[z[i] + i] == s[z[i]])) z[i]++;
}
if(z[i] > p) {
p = z[i]; k = i;
}
}
}