前綴函數

我個人覺得 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() {}