题解 P3375 【【模板】KMP字符串匹配】
本题解主要讲解nxt数组的构造及优化
蒟蒻题解，大佬勿喷
相信大家对朴素算法已经很了解了，所以我们直接步入正题（原谅我的偷懒）
约定：字符串的开头编号为0，文本为t，模版为p，t，p的长度为lt，lp
首先，kmp的行为就是利用之前的匹配情况，不移动t，只移动p来完成字符串匹配
所以假设有一个nxt数组，表示当匹配到p的第j号时发现不对，于是将j移动到nxt[j]继续匹配，直到j==0（模版开头，表示这个t[i]无法成为p中的任何部分）或者t[i]==p[j]（匹配成功）
接下来，如果匹配成功，则++j，如果j==lp（全部匹配成功），则输出开头位置（i-lp+2）
于是我们非常偷懒地假设这个nxt数组已经完成了，于是匹配代码如下
for (int i(0), j(0); i < lt; ++i) {
while (j&&t[i] ^ p[j])j = nxt[j];
if (t[i] == p[j])++j;
if (j == lp)printf("%i\n", i - lp + 2);
}现在我们来考虑nxt数组的构造（该来的还是要来啊）
因为nxt数组利用之前的结果，所以当nxt[i]>=1时p中0~nxt[j]-1的部分与j-nxt[j]~j-1的部分必然完全一样
首先引入一个叫做前缀后缀的概念（假设有个叫做s的字符串，长度ls）
前缀 ：空，s[0]，s[0]~s[1]，s[0]~s[2]，s[0]~s[3]……s[0]~s[ls-2]
后缀 ：空，s[ls-1]，s[ls-2]~s[ls-1]，s[ls-3]~s[ls-1]，s[ls-4]~s[ls-1]……s[1]~s[ls-1]
注意：前缀后缀可以是空，但整个字符不可以是前缀后缀
所以nxt[j]表示的就是在j之前的最长的完全相同的前缀后缀长度（大家请想一想）
假设有字符串ababac
那么对应的nxt：{0，0，0，1，2，3，0}（注意这不含单调性）
于是可以用递推的方法求nxt（其实就是用自己匹配自己）（初始化nxt[0]=nxt[1]=0，i=1，j=0）
首先像前面一样，一直j=nxt[j]直到跑到开头或者p[i]==p[j]（匹配成功）
如果匹配成功，那么nxt[i+1]=j+1；否则nxt[i+1]=0
最后j=nxt[++i]，为下次递推作准备，直到i==lp
构造nxt数组代码如下
for (int i(1), j(0); i < lp; j = nxt[++i]) {
while (j&&p[i] ^ p[j])j = nxt[j];
if (p[i] == p[j])nxt[i + 1] = j + 1;
}于是丑陋的AC代码
#include<cstdio>
#include<cstring>
using namespace std;
char t[1000001], p[1000001];
int nxt[1000001], lt, lp;
int main() {
scanf("%s%s", t, p), lt = strlen(t), lp = strlen(p);
for (int i(1), j(0); i < lp; j = nxt[++i]) {
while (j&&p[i] ^ p[j])j = nxt[j];
if (p[i] == p[j])nxt[i + 1] = j + 1;
}
for (int i(0), j(0); i < lt; ++i) {
while (j&&t[i] ^ p[j])j = nxt[j];
if (t[i] == p[j])++j;
if (j == lp)printf("%i\n", i - lp + 2);
}
for (int i(1); i <= lp; ++i)printf("%i ", nxt[i]);
getchar(), getchar(); return 0;
}注意！！还没完！！
其实上文根本不是正版kmp算法（也不知道为什么AC），而是未优化的mp算法，正版kmp对nxt数组的构造做了优化（说实在也没什么）
因为当匹配失败时，j要移到nxt[j]，但如果p[j]==p[nxt[j]]，那么匹配必然又失败，这就做了无谓的工作
所以递推时，如果p[i+1]==p[j+1]，那么nxt[i+1]应该=nxt[j+1]
于是就有了优化的nxt构造代码
for (int i(1), j(0); i < lp;) {
while (j&&p[i] ^ p[j])j = nxt[j];
if (p[i++] == p[j++])nxt[i] = (p[i] ^ p[j] ? j : nxt[j]);
else j = 0;
}然后就是优化的全部代码
#include<cstdio>
#include<cstring>
char t[1000001], p[1000001];
int nxt[1000001], lt, lp;
int main() {
scanf("%s%s", t, p), lt = strlen(t), lp = strlen(p);
for (int i(1), j(0); i < lp;) {
while (j&&p[i] ^ p[j])j = nxt[j];
if (p[i++] == p[j++])nxt[i] = (p[i] ^ p[j] ? j : nxt[j]);
else j = 0;
}
for (int i(0), j(0); i < lt; ++i) {
while (j&&t[i] ^ p[j])j = nxt[j];
if (t[i] == p[j])++j;
if (j == lp)printf("%i\n", i - lp + 2);
}
for (int i(1); i <= lp; ++i)printf("%i ", nxt[i]);
getchar(), getchar(); return 0;
}本人洛谷测试21分（意料之中，是因为nxt数组变了），但根据与前文程序的对拍，在匹配上没有问题，仅供参考，如果出现问题，望大佬们多多指教