kmp总结（个人笔记）
柒葉灬
2018-12-27 22:04:58
# $KMP$算法总结
-------
$kmp$算法就是用来找 $string \ \ \ S$ 中存在多少个 $ string \ \ \ T $ ，时间复杂度为$O(n+m)$
>不在多叙述kmp算法，这不是算法学习~~（懒）~~。
-------
$kmp$ 算法中常常会有一个 $nxt$ 数组，维护的是最长的**真前后缀**匹配。
>这是一段后来加的ps：
>china 的 前缀：c , ch, chi, chin ,china
>china 的真前缀：c , ch , chi, chin
模板代码：
```cpp
void Getnxt(){
nxt[1]=0;
int j=0;
for(int i=2;i<=lent;i++){
while(j && t[i]!=t[j+1])
j=nxt[j];
if(t[i]==t[j+1])
j++;
nxt[i]=j;
}
}
```
------------
有了$nxt$数组就可以查询了。
模板代码：
```cpp
int Findans(){
int j=0,ans=0;
for(int i=1;i<=lens;i++){
while(j && s[i]!=t[j+1])
j=nxt[j];
if(s[i]==t[j+1])
j++;
if(j==lent){
ans++;
j=nxt[j];
}
}
return ans;
}
```
>以上是基础
--------
[例题 专题G](https://cn.vjudge.net/contest/277011#problem/G)：
**题意**：给一个字符串 $S$，问最多可以拆成多少个子串 $T$ ，使得 $S$ 由若干个 $T$ 组成，如：$S="ababab"\ \ , \ \ T="ab"$
**思路**：比如说题意中的$S="ababab"$，
我们把$nxt$全部~~打表~~写出来。
得到：$0 \ 0 \ 1 \ 2 \ 3 \ 4 $
惊喜发现$ 1 \ 2 \ 3 \ 4 $**很有规律**。
仔细分析：从第二个 $T$ 开始，接下来的$nxt$数组全部都是递增的。（显然正确）
可以从最后一个$nxt$数值里面推出$T$的长度，判断一下是否可以整除就行了。
```cpp
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1e6+5;
char str[maxn];
int n,nxt[maxn];
void Getnxt(){
int j=0;
nxt[1]=0;
for(int i=2;i<=n;i++){
while(j&&str[i]!=str[j+1])
j=nxt[j];
if(str[i]==str[j+1])
j++;
nxt[i]=j;
}
}
int main(){
while(scanf("%s",str+1),str[1]!='.'){
n=strlen(str+1);
Getnxt();
int cnt=nxt[n];
int len=n-cnt;
if(cnt%len==0){
printf("%d\n",cnt/len+1);
}else puts("1");
}
return 0;
}
```
-----------
[例题 专题J](https://cn.vjudge.net/contest/277011#problem/J)：
**题意**：给定一个字符串$S$，其中有一些字符是位置的$?$，再给一个字符串$T$，问$T$最多可以在$S$出现多少次。
**思路**：需要用$dp$，考虑遇到$?$一定是要匹配的，（不匹配 = 后面不选）。但是匹配不一定是匹配当前这一位，可能往$nxt$上走，所以来一个后缀最大值就可以了，倒着扫一遍，详细见代码。还有就是不是问号的情况，（套了个$while$复杂度玄学，但可以优化预处理，因为过了就没有继续优化了）直接模拟就行了。
```cpp
#include<bits/stdc++.h>
#define debug(x) cerr<<"\t"<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=1e5+5;
template<class T>inline void tomax(T &a,T b){if(a<b)a=b;}
char s[maxn],t[maxn];
int ans,lens,lent;
int nxt[maxn],dp[maxn*105],tmp[maxn];
#define dp(i,j) dp[(i)*lent+(j)]
void Getnxt(){
nxt[1]=0;
int j=0;
for(int i=2;i<=lent;i++){
while(j&&t[i]!=t[j+1])
j=nxt[j];
if(t[i]==t[j+1])
j++;
nxt[i]=j;
}
}
int main(){
scanf("%s%s",s+1,t+1);
lens=strlen(s+1);
lent=strlen(t+1);
if(lent>lens)return puts("0"),0;
Getnxt();
memset(dp,-63,sizeof(dp));
dp(0,0)=0;
for(int i=1;i<=lens;i++){
if(s[i]=='?'){
for(int j=0;j<lent;j++){
tmp[j]=dp(i-1,j);
}
for(int j=lent-1;j>0;j--){
tomax(tmp[nxt[j]],tmp[j]);
}
for(int j=1;j<lent;j++){
dp(i,j)=tmp[j-1];
}
tomax(dp(i,nxt[lent]),tmp[lent-1]+1);
}else {
for(int j=0;j<lent;j++){
if(dp(i-1,j)<0)continue;
int k=j;
while(k&&s[i]!=t[k+1])
k=nxt[k];
if(s[i]==t[k+1])
k++;
if(k==lent){
tomax(dp(i,nxt[lent]),dp(i-1,j)+1);
}else {
tomax(dp(i,k),dp(i-1,j));
}
}
}
}
for(int i=1;i<=lens;i++)
for(int j=0;j<lent;j++)
tomax(ans,dp(i,j));
cout<<ans<<endl;
return 0;
}
```
----------
[例题 专题K](https://cn.vjudge.net/contest/277011#problem/K)：
**题意**：字符串可以被压成 数字+字符串的形式，比如说$"aaaa"="4a"$，问给出的字符串$S$最少被压成多少。（注意$10$占$2$个位置）。
**思路**：可以写$O(n^2)$的$dp$，所以只要求出压一个区间的最小代价就行了。就是上面 专题G 的升级版。
```cpp
#include<bits/stdc++.h>
#define debug(x) cerr<<"DEBUG\t"<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=8e3+5;
int n,dp[maxn],dis[maxn][maxn];
char str[maxn];
int nxt[maxn];
void check(int s){
nxt[s]=s-1;
int j=s-1;
for(int i=s+1;i<=n;i++){
while(j>=s&&str[i]!=str[j+1])
j=nxt[j];
if(str[i]==str[j+1])
j++;
nxt[i]=j;
}
for(int i=s;i<=n;i++){
int cnt=nxt[i]-(s-1);
int len=i-s+1-cnt;
if(cnt%len!=0){
dis[s][i]=i-s+2;
}else {
int C=cnt/len+1;
int S=len,tmp=0;
while(C){tmp++;C/=10;}
dis[s][i]=S+tmp;
}
}
}
int main(){
scanf("%s",str+1);
n=strlen(str+1);
for(int i=1;i<=n;i++)
check(i);
memset(dp,63,sizeof(dp));
dp[0]=0;
for(int i=1;i<=n;i++)
for(int j=0;j<i;j++)
dp[i]=min(dp[i],dp[j]+dis[j+1][i]);
cout<<dp[n]<<endl;
return 0;
}
```
--------------
>$kmp$算法所解决的问题十分有限，就是可以维护一个最长相同前缀。
>尤其要记住$kmp$算法的核心：不做重复的比较。
>不能干贪心的傻事，$n$给你$5000$，你写了个$O(n^2)$，您觉得合适吗