Morrison Pratt
コードについての説明(個人的メモ)
文字列 $S$ が与えられたときに $0 \le i < n$ について $S[0:i]$ の接頭辞と接尾辞が最大何文字一致しているかを表す配列 $res[i]$ を線形時間で構築するアルゴリズム(ただし $res[i] \le i$ とする).
時間計算量: $\O (|S|)$
コード
void MP(const string& S, vector<int>& res){
int n = (int)S.size(), j = 0;
res.resize(n, 0);
for(int i = 0; i < n-1; i++){
while(S[i+1] != S[j] && --j >= 0) j = res[j];
res[i+1] = ++j;
}
}