洛谷 P2375 [NOI2014] 动物园(kmp理解题)

题目

bzoj3670

对于字符串S的前i个字符构成的子串，

既是它的后缀同时又是它的前缀，并且该后缀与该前缀不重叠，将这种字符串的数量记作num[i]

例如S为aaaaa，则num[4] = 2。

这是因为S的前4个字符为aaaa，其中a和aa都满足性质‘既是后缀又是前缀’，

同时保证这个后缀与这个前缀不重叠。

而aaa虽然满足性质‘既是后缀又是前缀’，

但遗憾的是这个后缀与这个前缀重叠了，所以不能计算在内。

同理，num[1] = 0,num[2] = num[3] = 1,num[5] = 2。

给定n(n<=5)组样例，每次给出一个长为l(l<=1e6)的小写字母串，

求所有(num[i]+1)的乘积，答案对1e9+7取模

思路来源

https://www.luogu.com.cn/blog/dedicatus545/solution-p2375

题解

仔细推根据kmp新构造的num的定义发现，

i的贡献dp[i]，即为，从i跳next数组，即next[i]，next[next[i]]连跳，

跳到第一个<=i/2的位置后开始计数，继续跳next数组，跳到位置为0的总次数

于是一个比较自然的想法是，倍增一下，然后处理出第一次跳到<=i/2的位置和跳到0的位置

但是只能过l<=5e5的小数据，只有80分，yyb换了两维就100分了很迷惑

于是考虑O(n)做法，利用了fail数组的性质，

 考虑在计算fail数组时，从i到i+1多了一个字母，而fail[i+1]一开始是在j=fail[i]的基础上回跳的，

（可以认为是，类似AC自动机的，next字母的fail，等于fail的next字母）

跳到第一个与a[i]相等的位置j，然后对j加一

这里要求fail[i+1]<=(i+1)/2，即不妨找到fail[i+1]的对应j之后，

对j继续回跳，使之满足小于等于(i+1)/2的条件，

注意到fail数组的前一部分仍有fail数组的性质，所以仍可进行后续递推

找到了i跳fail树跳到的第一个满足j<=i/2的位置之后，只需连加j跳到根的次数，

这个可以在fail树上做个父到子的递推，num[j]=num[fail[j]]+1，这样复杂度就是O(n)的了

代码1（80分）

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=20,mod=1e9+7;
char a[N];
int T,n,m,f[N][M],dp[N];
void getFail(){
	f[0][0]=f[1][0]=0;
	for(int i=1;i<n;i++){
		int j=f[i][0];
		while(j && a[i]!=a[j]){
			j=f[j][0];
		}
		f[i+1][0]=(a[i]==a[j]?j+1:0);
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<M;++j){
			//printf("f:%d\n",f[i][j-1]);
			f[i][j]=f[f[i][j-1]][j-1];
		} 
	}
	dp[0]=0;
	for(int i=1;i<=n;i++){
		int now1=i,now2=i,num1=0,num2=0;
		for(int k=M-1;k>=0;--k){
			//printf("now1:%d now2:%d\n",now1,now2);
			if(f[now2][k]>i/2)now2=f[now2][k],num2+=1<<k;
			if(f[now1][k]>0)now1=f[now1][k],num1+=1<<k;
		}
		/*
		int j=f[i],num1=0,num2=0;
		while(j>i/2)j=f[j],num1++,num2++;
		while(j)j=f[j],num1++;
		*/
		dp[i]=num1-num2;
		//printf("dp[%d]:%d\n",i,dp[i]);
		m=1ll*m*(dp[i]+1)%mod;
	}
}
int main(){
	scanf("%d",&T);
	while(T--){
		m=1;
		scanf("%s",a);
		n=strlen(a);
		getFail();
		printf("%d\n",m);
	}
	return 0;
}

代码2（100分）

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=20,mod=1e9+7;
char a[N];
int T,n,m,f[N],num[N];
void getFail(){
	f[0]=f[1]=0;
	num[0]=0;num[1]=1;
	int j;
	j=0;
	for(int i=1;i<n;i++){
		while(j && a[i]!=a[j]){
			j=f[j];
		}
		j+=(a[i]==a[j]);
		f[i+1]=j;
		num[i+1]=num[j]+1;
	}
	j=0;
	for(int i=1;i<=n;i++){
		while(j && a[i]!=a[j]){
			j=f[j];
		}
		j+=(a[i]==a[j]);
		while((j<<1)>(i+1)){
			j=f[j];
		}
		//printf("dp[%d]:%d\n",i,dp[i]);
		m=1ll*m*(num[j]+1)%mod;
	}
}
int main(){
	scanf("%d",&T);
	while(T--){
		m=1;
		scanf("%s",a);
		n=strlen(a);
		getFail();
		printf("%d\n",m);
	}
	return 0;
}