洛谷p2375 kmp

题意

给你一个字符串，让你求一个\(num\)数组，\(num[i]\)为长度为\(i\)的前缀的公共前后缀长度不超过\(\lfloor \frac{i}{2}\rfloor\)的个数，

例如"\(aaaaa\)",\(num[1]=0,num[2]=num[3]=1,num[4]=num[5]=2.\)

分析

设数组\(dp[i]\)为长度为\(i\)的前缀的所有公共前后缀个数,则\(num[i]=dp[j]\),\(j\)为\(i\)的\(next\)祖先中刚好小于\(i\)的一半的那个数。求\(dp[i]\)可以在求\(next\)数组过程中递推求出。

Code

#include<bits/stdc++.h>

#define fi first

#define se second

#define pb push_back

#define ll long long

using namespace std;

const int inf=1e9;

const int mod=1e9+7;

const int maxn=1e6+10;

int nex[maxn],n,T;

ll dp[maxn];

char s[maxn];

int main(){

	//ios::sync_with_stdio(false);

	//freopen("in","r",stdin);

	scanf("%d",&T);

	while(T--){

		memset(nex,0,sizeof(nex));

		memset(dp,0,sizeof(dp));

		scanf("%s",s+1);

		n=strlen(s+1);

		dp[1]=1;ll ans=1;

		for(int i=2,j=0;i<=n;i++){

			while(j&&s[i]!=s[j+1]) j=nex[j];

			if(s[i]==s[j+1]) ++j;

			nex[i]=j;dp[i]=dp[j]+1;

		}

		for(int i=2,j=0;i<=n;i++){

			while(j&&s[i]!=s[j+1]) j=nex[j];

			if(s[i]==s[j+1]) ++j;

			while(j>i/2) j=nex[j];

			ans=ans*(dp[j]+1)%mod;

		}

		printf("%lld\n",ans);

	}

	return 0;

}

巴特西

洛谷p2375 kmp

题意

分析

Code

最新文章

热门文章