前缀函数
给定一个长度为 \(n\) 的字符串 \(s\)（设下标从 \(1\) 开始），其 前缀函数 定义为一个长度为 \(n\) 的整数数组 \(\pi\)，其中 \(\pi_i\) 满足：
- \(s[1,\pi_i]=s[n-\pi_i+1,n]\) 且 \(\pi_i \ne n\)。
- 如果没有为 \(0\)。
最朴素的方法求 \(\pi\) 时间复杂度为 \(O(n^3)\)。
优化 1
结论：\(\pi_{i+1} \le \pi_{i}+1\)。
每次当前字符串扩大一位，如果 \(s'[\pi_i+1]=s'[i+1]\)，那么 \(\pi_{i+1}=\pi_{i}+1\)，反之，\(\pi_{i+1} \le \pi_{i}\)。
这样时间复杂度降至 \(O(n^2)\)。
优化 2
当 \(s'[\pi_i+1]=s'[i+1]\) 时 \(\pi_{i+1}=\pi_{i}+1\)，那么当 \(s'[\pi_i+1] \ne s'[i+1]\) 时，我们需要找到一个长度 \(j\) 使得 \(s'[1,j]=s'[i-j+2,i+1]\)。可以发现：
\[s[1,j]=s[i-j+2,i+1]=s[\pi_{i}-j+1,\pi_{i}] \]此时 \(j=\pi_{\pi_{i-1}}\)，因此我们得到 \(j_{n}=\pi_{j_{n-1}-1}\)。
时间复杂度降至 \(O(n)\)。
// 此处 s 的下标从 1 开始
for (int i = 1; i < n; i++) {
int j = pi[i - 1];
while (j > 0 && s[i] != s[j]) {
j = pi[j - 1];
}
if (s[i] == s[j]) {
j++;
}
pi[i] = j;
}
查找子串（KMP 算法）
给定字符串 \(s,t\)，长度分别为 \(n,m\)，求 \(t\) 在 \(s\) 中出现的下标。
设字符串 \(M=t+\#+s\)，其中 \(\#\) 替换为 \(s,t\) 中不存在的字符。这样 \(\pi_{1 \sim m}\) 均 \(<m\)，\(\#\) 所在位置一定为 \(0\)，此后当 \(\pi_i=m\) 时说明 \(s\) 中出现 \(t\)，下标为 \(i-2m\)。
由于长度永远不会超过 \(m\)，因为中间的 \(\#\)，所以只需求出 \(t\) 的前缀数组即可，对 \(s\) 维护变量 \(j\)。
for (int i = 0, j = 0; i < n; i++) {
while (j > 0 && b[j] != a[i]) {
j = pi[j - 1];
}
if (b[j] == a[i]) {
j++;
}
if (j == m) {
cout << i - m + 2 << "\n";
}
}