题目链接
洛谷 P3375 【模板】KMP
KMP 模板题
border：公共前后缀，即若字符串 \(t'\) 是 \(s'\) 的 border，那么 \(t'\) 既是 \(s'\) 的前缀，又是 \(s'\) 的后缀。
模式串、文本串：对于模式串 / 字符串匹配算法，要在文本串中匹配模式串，即在文本串中找出模式串。
声明：下文中字符串第 \(i\) 位均从 \(1\) 开始，如字符串
abcab的第三位是c。
算法介绍
KMP 算法，由 D.E.Knuth、J.H.Morris、V.R.Pratt 三位科学家共同发明，是一种具有线性时间复杂度的模式串匹配算法，即在文本串 \(s\) 中找出所有与模式串 \(t\) 完全相同的字串只需要 \(O(|s|+|t|)\) 的优秀复杂度。
思路分析
对于一般的 BF（Brute Force）算法（即最朴素的暴力枚举），每次失配后，我们都需要回到模式串的开头重新匹配，时间复杂度最坏可达到 \(O(|s|\times|t|)\)。
而对于 KMP 算法，我们发现，在图中第一次匹配完成后，可以直接将模式串的第一个字符 a 移到文本串的第三个字符 a，而无需一个个遍历过来。那么如何实现呢？我们观察发现，这个 a 既是模式串 aba 的前缀，也是它的后缀，即这个 a 是模式串的公共前后缀，所以移过来之后这个 a 仍然匹配。
再举一个例子，模式串为 abcabd，文本串为 abcabcababcad。当我们匹配到第六位时发现失配（即当前字符不同），由于模式串前五位 abcab 的最长公共前后缀为 ab，所以我们可以直接把模式串的第三位移至文本串的第六位进行匹配，省去了中间的遍历。
即对于模式串匹配出现失配时，记当前已经匹配好了模式串前 \(j\) 位，其最长公共前后缀长度为 \(kmp_j\)，对于模式串第 \(j+1\) 位，若对应文本串第 \(i\) 位与其不同，那么只需移动模式串，使 \(j=kmp_j\)，再进行比较，直至 \(j=0\) 或下一位匹配成功即可。
通过借助已匹配部分的公共前后缀，我们可以进行更高效率的模式串移动。
for (int i=1,j=0;i<=n;++i){ // s1 为文本串，s2 为模式串while (j && s2[j+1]!=s1[i]) j=kmp[j]; // 模式串移动if (s2[j+1]==s1[i]) ++j; // 尝试匹配if (j==m) printf("%d\n",i-j+1),j=kmp[j]; // 模式串全部匹配成功
}
接下来考虑计算 \(kmp_i\)。还是以 abcab 解释，我们发现其最长公共前后缀为 ab，即如果用模式串取匹配本身，模式串的前缀 ab 可以匹配到后缀 ab。又因为只能让真前缀匹配真后缀，所以应该从作为文本串的模式串的第 \(2\) 位开始匹配。每次循环最后，作为文本串的模式串第 \(i\) 个字符成功匹配模式串第 \(j\) 个字符，说明模式串前 \(i\) 个字符组成的字符串的前 \(j\) 位（在模式串中）可以匹配后 \(j\) 位（在“文本串”中，让 \(kmp_i\gets j\) 即可。
for (int i=2,j=0;i<=m;++i){while (j && s2[j+1]!=s2[i]) j=kmp[j];if (s2[j+1]==s2[i]) ++j;kmp[i]=j;
}
代码呈现
#include<bits/stdc++.h>
using namespace std;const int N=1e6+10;
int kmp[N];
char s1[N],s2[N];int main(){scanf("%s%s",s1+1,s2+1);int n=strlen(s1+1),m=strlen(s2+1);for (int i=2,j=0;i<=m;++i){while (j && s2[j+1]!=s2[i]) j=kmp[j];if (s2[j+1]==s2[i]) ++j;kmp[i]=j;}for (int i=1,j=0;i<=n;++i){while (j && s2[j+1]!=s1[i]) j=kmp[j];if (s2[j+1]==s1[i]) ++j;if (j==m) printf("%d\n",i-j+1),j=kmp[j];}for (int i=1;i<=m;++i) printf("%d ",kmp[i]);return 0;
}