前缀函数

我个人觉得 oiwiki 上的学习顺序是很合理的，学 KMP 之前先了解前缀函数是非常便于理解的。

前后缀定义

前缀 $prefix$ 指的是从字符串 $S$ 的首位到某个位置 $i$ 的一个子串，这样的子串写作 $prefix(S,i)$。

后缀 $suffix$ 指的是从字符串 $S$ 的某个位置 $i$ 到末尾的一个子串，这样的子串写作 $suffix(S,i)$。

$S$ 的 真前缀 指的是不等于 $S$ 的一个前缀，$S$ 的 真后缀 指的是不等于 $S$ 的一个后缀。

如 $S=aab$，那么 $aab$ 是 $S$ 的一个前缀，但不是 $S$ 的真前缀，是 $S$ 的后缀，但不是 $S$ 的真后缀。

前缀函数定义

给定一个长度为 $n$ 的字符串 $s$，其 前缀函数 写作 $\pi$ ，则 $\pi (i)$ 的定义为子串 $s[\mathrm{0...}i]$ 的 最长相等真前缀与真后缀 长度。

意思就是

1. 如果子串 $s[\mathrm{0...}i]$ 有一对相等的真前缀与真后缀，那么 $\pi (i)$ 就是这个相等的真前缀的长度。
2. 如果有多对相等的，$\pi (i)$ 取最长的一对作为答案。
3. 如果不存在相等，那么 $\pi (i)=0$。

如 $s=aabba$，则 $\pi (0)=0,\pi (1)=1,\pi (2)=0,\pi (3)=0,\pi (4)=1$。

其中 $\pi (0)$ 表示字符串 $a$ 的最长相等真前缀与真后缀，由于 $a$ 长度为 $1$，所以没有真前缀，故 $\pi (0)=0$。

其中 $\pi (4)$ 表示字符串 $aabba$ 的最长相等真前缀与真后缀，答案是 $a$，故 $\pi (4)=1$。

前缀函数的求法

朴素算法

利用双重循环，第一重循环枚举 当前子串长度 $s[\mathrm{0...}i]$，第二层循环枚举子串的所有 真前缀的长度，长度从大到小枚举，并判断当前真前缀与真后缀是否相同，如果相同的话当前长度就等于 $\pi (i)$。

for (int i = 1; i < s.size(); i++) {for (int j = i; j >= 0; j--) {if (s.substr(0, j) == s.substr(i - j + 1, j)) {p[i] = j;break;}}
}

其中 s.substr(pos, len) 是字符串的一个函数，意思是提取出 $s$ 从 $pos$ 位置开始往下数 $len$ 个字符的子串，等价于子串 $s[pos...pos+len-1]$，要减 $1$ 是因为从 $pos$ 开始，$pos$ 也算一个字符。

所以 s.substr(0, j) 表示的是子串 $s[\mathrm{0...}j-1]$，s.substr(i - j + 1, j) 表示的是子串 $s[i-j+1,i]$。

该算法的时间复杂度是 $O(n^3)$。

优化一

当我们求 $\pi (i)$ 的时候，我们没有 充分运用 之前求过的 $\pi$ 值。

对于 $s[\mathrm{0...}i]$，考虑如何充分利用 $\pi (i-1)$ ：

1. $\pi (i-1)=0$，说明 $\pi (i)$ 的值 至多 为 $1$。如果 $\pi (i)$ 的值大于 $1$，说明 $s[\mathrm{0...}i-1]$ 的最长相等真前缀与后缀的长度至少为 $1$，与 $\pi (i-1)=0$ 矛盾。
2. $\pi (i-1)\ne 0$，如果 $s[i]==s[\pi (i-1)]$，那么 $\pi (i)=\pi (i-1)+1$。否则 $\pi (i)$ 的大小必然小于等于 $\pi (i-1)$。

不难发现，$\pi (i)$ 的 上限至多 比 $\pi (i-1)$ 多 $1$，所以第二重循环只需要从 $\pi (i-1)+1$ 枚举即可。

for (int i = 1; i < s.size(); i++) {for (int j = p[i - 1] + 1; j >= 0; j --) {if (s.substr(0, j) == s.substr(i - j + 1, j)) {p[i] = j;break;}}
}

关于时间复杂度的计算，当我们计算 $\pi (i)$ 的时候 多枚举 了 $x$ 次，说明 $\pi (i)$ 的值相对于 $\pi (i-1)$ 减少了 $x$。也就是说 $\pi (i+1)$ 的第二重循环的上限也就 减少 了 $x$。

也就是说，多增加的次数，在后续的求解中会被抵消，那么就只剩下了最终至少需要枚举的第一次。

所以第二重循环的时间就主要在 substr 函数的 $O(n)$ 上，故总时间复杂度为 $O(n^2)$。

优化二

第二重循环从 $\pi (i-1)+1$ 开始遍历，每次判定还是依靠了 substr，有没有不用 substr 的方法？

如果想不用 substr 就能判断前缀后缀是否相等，说明我们就得跳到 前缀后缀一定相等 的位置。

也就是说当 $s[\pi (i-1)]\ne s[i]$ 的时候，我们就得找到一个仅次于 $\pi (i-1)$ 的长度 $j$，使得 $s[\mathrm{0...}j-1]=s[i-j...i-1]$，如果找到了这样的 $j$，我们再判断 $s[j]$ 和 $s[i]$ 是否相等就行了。

如果相等，说明 $\pi (i)=j$，否则我们就找下一个仅次于 $j$ 的长度 … 直到 $j$ 削减为 $0$，此时 $\pi (i)=0$。

我们可以看到这张图，当 $s[\pi (i-1)]$ 与 $s[i]$ 匹配失败，我们就要找一个仅次于 $\pi (i-1)$ 的长度 $j$，使之满足$s[\mathrm{0...}j-1]=s[i-j...i-1]$，在图上就是深红色的两个位置。

又因为一定有 $s[\mathrm{0...}p[i-1]-1]=s[i-p[i-1]...i-1]$ 成立，这是 $\pi (i-1)$ 的定义，所以可以认为 $s[\mathrm{0...}p[i-1]-1]$ 的 后缀必然有一个长度为 $j$ 的子串 等于 $s[i-j...i-1]$。

又因为 $s[\mathrm{0...}p[i-1]-1]$ 的 前缀必然有一个长度为 $j$ 的子串 等于 $s[i-j...i-1]$，所以 $s[\mathrm{0...}p[i-1]-1]$ 有 一对相等的前后缀，其长度为 $j$。

所以我们可以得出，下一个长度仅次于 $\pi (i-1)$ 的长度 $j$ 等于 $\pi (\pi (i-1)-1)$。

于是，我们就可以省略掉 substr 的 $O(n)$，只需要每次去比较 $s[j]$ 和 $s[i]$ 是否相等即可。

经过两次优化，求前缀函数的算法的时间复杂度为 $O(n)$。

void getPrifixFunction () {p[0] = 0;for (int i = 1; i < n; i++) {int j = p[i - 1];while (j && s[j] != s[i]) {j = p[j - 1];}if (s[j] == s[i]) j ++;p[i] = j;}}

这串代码似乎和上面描述的有一些出入，所以这里解释一下每一句话。

首先 getPrifixFunction 是求前缀函数的函数，前缀函数的第一个值 $p[0]=0$。

然后枚举所有长度的子串 $s[\mathrm{0...}i]$，最初 $j$ 是满足 $s[\mathrm{0...}j-1]=s[i-j...i-1]$ 的最大长度 $\pi (i-1)$。

然后循环判断是否 $s[j]==s[i]$，如果不等于那么就往下跳到下一个长度 $j=\pi (j-1)$。

最后特判一下长度为 $1$ 的情况，因为长度为 $1$ 的时候是 $s[0]==s[i]$，所以 $j$ 已经削减到 $0$ 了。

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
#define int long long
#define endl '\n'
#define PII pair<int,int>
#define INF 1e18
const int N = 1e6 + 7;struct PrifixFunction {int n;string s;vector <int> p;PrifixFunction (int _n, string _s) : s(_s), n(_n), p(_n + 1){}void getPrifixFunction () {p[0] = 0;for (int i = 1; i < n; i++) {int j = p[i - 1];while (j && s[j] != s[i]) {j = p[j - 1];}if (s[j] == s[i]) j ++;p[i] = j;}}};signed main() {}