社区讨论

为什么num[1]=1

P2375[NOI2014] 动物园参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mlywbaz3
此快照首次捕获于
2026/02/23 16:09
2 周前
此快照最后确认于
2026/02/25 14:42
2 周前
查看原帖

RT

为什么不是num[1]=0
CPP
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
const int maxn=1e6+10;
const long long mod=1e9+7;
int nex[maxn],num[maxn];
int main(){
	ios::sync_with_stdio(false);
    cin.tie(0);
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		memset(nex,0,sizeof(nex));
		memset(num,0,sizeof(num));
		string s;
		cin>>s;
		int len=s.size();
		s="#"+s;
		int k=0;
		num[1]=1;//为什么要=1
		for(int j=2;j<=len;j++){
			while(k>0&&s[j]!=s[k+1])k=nex[k];
			if(s[k+1]==s[j])k++;
			nex[j]=k;
			num[j]=num[k]+1;
		}
		k=0;
		long long ans=1;
		for(int j=2;j<=len;j++){
			while(k>0&&s[j]!=s[k+1])k=nex[k];
			if(s[j]==s[k+1])k++;
			while(k*2>j)k=nex[k];
			ans=ans*(num[k]+1)%mod;
		}
		cout<<ans<<"\n";
	}
}

回复

0 条回复,欢迎继续交流。

正在加载回复...