kmp
人殇物已非
·
·
个人记录
补一下之前没写题解的那些板子之 kmp算法
#### 定义：
$next[i]$表示对于从字符串起点到$i$这个前缀子串中，满足该字串的前缀等于后缀的最长长度。
#### 性质：
- 对于$next[i]$，很显然地满足：$next[i]<=next[i-1]+1$。
可以想到，对于$i-1$满足的最长前缀$==$后缀，给后面加上一个字符最多只能使得$i-1$满足的前后缀长度$+1$，而如果当前$i$和$i-1$前缀的后一个字符失配了，$next[i]$只能更小。若是更大则不可能失配。
- 对于$next[i]$与$next[next[i]]$，记$j=next[i]$，即$1...j$的字串既是$i$的前缀，又是$i$的后缀，那么对于$next[j]$为$j$的前缀和$j$的后缀，就也为$i$的前缀和$i$的后缀。且由于$next$数组是满足条件的最大值，$next[next[i]]$就是当$next[i]$不选时仅次于它的最长答案。
#### 维护：
由上面的性质， 可以得出求$next[i]$的思路，找到一个$i-1$的前缀往后延申一个字符刚好等于$s[i]$，且这个前缀要尽量长。
那么在$next[i-1]=k$时：
```cpp
while(s[k+1]!=s[i]) k=next[k];
```
找到这样的前缀，如果找不到则为0。
随后如果找到了这个前缀，$next[i]$即为$k+1$，不然则为0。
由于在循环时$k$的值会一直保留，则$i++$时，k刚好为$next[i-1]$，故写起来十分优美简洁。
（该代码字符串采用$1$到$n$即$[1,n]$保存，若采用$1$到$n-1$即$[0,n)$，$s[k]$即已经为$i-1$的前缀往后延申一个字符，不写成$s[k+1]$）
```cpp
nxt[1]=0;
int k=0;
for(int i=2;i<=len2;i++){
while(k&&s2[i]!=s2[k+1])k=nxt[k];
nxt[i]=s2[i]==s2[k+1]?++k:0;
}
```
#### 查询：
$kmp$其实也是一个自动机（或称状态机）。
只不过$kmp$相当于在一条链上做自动机从前往后匹配，每当失配跳到失配指针$fail[i]$判断下一个，一直跳$fail$就可以了。（这里$fail$就是$next$)
```cpp
k=0;
for(int i=1;i<=len1;i++){
while(k&&s1[i]!=s2[k+1])k=nxt[k];
k+=s1[i]==s2[k+1]?1:0;
if(k==len2)
//you have found one
}
```
对于$luogu$的这个模板题，贴一个完整代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000010;
char s1[maxn],s2[maxn];
int nxt[maxn];
int main(){
scanf("%s%s",s1+1,s2+1);
nxt[1]=0;
int len1=strlen(s1+1),len2=strlen(s2+1);
int k=0;
for(int i=2;i<=len2;i++){
while(k&&s2[i]!=s2[k+1])k=nxt[k];
nxt[i]=s2[i]==s2[k+1]?++k:0;
}
k=0;
for(int i=1;i<=len1;i++){
while(k&&s1[i]!=s2[k+1])k=nxt[k];
k+=s1[i]==s2[k+1]?1:0;
if(k==len2) printf("%d\n",i-len2+1);
}
for(int i=1;i<=len2;i++)
printf("%d ",nxt[i]);
return 0;
}
```