已过,但有疑问求助大佬
查看原帖
已过,但有疑问求助大佬
537046
大眼仔Happy楼主2023/8/2 11:38

我这样做,为什么是 num[1]=1\text{num}[1]=1,而不是 num[2]=1\text{num}[2]=1?

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+5;
const ll mod=1e9+7;
int T;
int n,fail[N],num[N];
ll ans;
char a[N];
//clearly understand
void GetFail()
{
	int j=0;
	for(int i=1;i<n;i++)
	{
		while(j&&a[i+1]!=a[j+1])j=fail[j];
		if(a[i+1]==a[j+1])j++;
		fail[i+1]=j;
		num[i+1]=num[j]+1;
	}
}
void GetNum()
{
	int j=0;
	for(int i=1;i<n;i++)
	{
		while(j&&a[i+1]!=a[j+1])j=fail[j];
		if(a[i+1]==a[j+1])j++;
		while(j*2>i+1)j=fail[j];
		ans=(ans*1ll*(num[j]+1))%mod;
	}
}
int main(){
	scanf("%d",&T);
	while(T--)
	{
		memset(fail,0,sizeof(fail));
		memset(num,0,sizeof(num));
		scanf("%s",a+1);n=strlen(a+1);
		ans=1;num[1]=1;
		GetFail();GetNum();
		printf("%lld\n",ans);
	}
	return 0;
}

2023/8/2 11:38
加载中...