关于KMP的一点思考
KMP的(next)数组的性质很精妙,有必要开一个坑学习一下
Part 1 啥是next
(next[i])表示对于(pre_i)这个字符串,这个抠出来的字符串本身后缀和前缀相等的最长长度。是一个自变量只和这个子串有关的函数。这点很重要
由于保证了是最长长度,这个数有一些优良的性质,常常在关于一个串的循环表示或者周期表示中发挥作用。
注意到这个(next[i])虽然代表是这个最长长度,但是值得注意的是,由于字符串从1开始编号,所以这个值也是那个前缀的下标。
Part2 如何求next
边界条件是,(nx[1]=0)。考虑我们若已经求得前面(i-1)的位置的(nx)值,现在如何求(nx[i])。
把(S[1dots i-1])看做一个整体,现在我们在后面加入了一个字符(S[i]=c)。
我们现在就是要在(pre_{nx[i-1]})中截一个最大的位置(p),使得(S[p+1]=c),而(p)虽然是下标,但是由于从(1)开始编号那么就同时就是这个串的长度,所以(nx[i]=p+1)。为什么是在(pre_{nx[i-1]})中找呢?因为我们要保证(S[i-p+1...i]=S[1,p])。
所以如何找(p)呢?由于我们要保证刚刚写的这个等式,可以发现(p)一定是在(G=(V,E),E=(x,nx[x]))这样的图中和(nx[i-1])联通的到祖先的链上,所以我们一直暴力跳(nx[])也就是遍历这条链,直到第一次找到一个位置(p)使得(S[nx[p]+1]=S[i])。
但是你可能觉得这样的复杂度是假的,下面我将证(复)明(读)暴力跳(nx[])遍历的复杂度不超过(O(n))
可以发现(nx[i]le nx[i-1]+1),得证。
哈哈哈哈
其实就是,(nx[i])的总增长是(O(n))的,而且一次最多增长(1),所以在其间不断跳的复杂度不超过(O(n))。(总共只有这么多(nx)给你跳啊!)
代码:
for(int t=2;t<=s2;++t){
nx[t]=nx[t-1];
while(nx[t]>0&&T[nx[t]+1]!=T[t]) nx[t]=nx[nx[t]];
if(T[nx[t]+1]==T[t]) ++nx[t];
}
Part 3 一些性质
由于我马上就要咕咕咕所以
P3435 [POI2006]OKR-Periods of Words
//@winlere
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define getchar() (__c==__ed?(__ed=__buf+fread(__c=__buf,1,1<<18,stdin),*__c++):*__c++)
using namespace std; typedef long long ll; char __buf[1<<18],*__c=__buf,*__ed=__buf;
inline int qr(){
register int ret=0,f=0;
register char c=getchar();
while(!isdigit(c))f|=c==45,c=getchar();
while(isdigit(c)) ret=ret*10+c-48,c=getchar();
return f?-ret:ret;
}
const int maxn=1e6+5;
char c[maxn];
int n,nx[maxn],cut[maxn];
inline void kmp(){
for(int t=2;t<=n;++t){
nx[t]=nx[t-1];
while(nx[t]>0&&c[nx[t]+1]!=c[t]) nx[t]=nx[nx[t]];
if(c[nx[t]+1]==c[t]) ++nx[t];
}
}
int Find(const int&p){
if(!nx[p]) return p;
if(cut[p]) return cut[p];
return cut[p]=Find(nx[p]);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
//freopen("out.out","w",stdout);
#endif
scanf("%d%s",&n,c+1);
kmp();
ll ans=0;
for(int t=1;t<=n;++t)
ans=(ans+t-Find(t));
printf("%lld
",ans);
return 0;
}
[P4824 USACO15FEB]Censoring (Silver) 审查(银)
//@winlere
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; typedef long long ll;
const int maxn=1e6+5;
char S[maxn],T[maxn];
pair<int,int> stk[maxn];
int s1,s2,top,nx[maxn];
int main(){
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
scanf("%s%s",S+1,T+1);
s1=strlen(S+1);
s2=strlen(T+1);
for(int t=2;t<=s2;++t){
nx[t]=nx[t-1];
while(nx[t]>0&&T[nx[t]+1]!=T[t]) nx[t]=nx[nx[t]];
if(T[nx[t]+1]==T[t]) ++nx[t];
}
int p=0;
for(int t=1;t<=s1;++t){
while(p&&T[p+1]!=S[t]) p=nx[p];
if(T[p+1]==S[t]) ++p;
stk[++top]=(pair<int,int>){t,p};
if(p==s2) top-=s2,p=stk[top].second;
}
for(int t=1;t<=top;++t) printf("%c",S[stk[t].first]);
putchar('
');
return 0;
}