为什么两种板子的写法一个连样例都过不了另一个却A了??? 0pts:
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5,Mod=1e9+7;
int n,nxt[N],num[N];
string s;
int getnext () {
memset(nxt,0,sizeof(nxt));
memset(num,0,sizeof(num));
int len = s.size();
nxt[0]=0;
nxt[1]=0;
num[0]=0;
num[1]=1;
for(int i=1;i<len;i++) {
int j=nxt[i];
while(j&&s[i]!=s[j]) {
j=nxt[j];
}
if(s[i]==s[j]) nxt[i+1]=j+1;
else nxt[i+1]=0;
num[i+1]=num[j]+1;
// cout<<i+1<<" : "<<nxt[j]<<"\n";
}
int ans=1;
for(int i=1;i<len;i++) {
int j=nxt[i];
while(j&&s[i]!=s[j]) {
j=nxt[j];
}
while(j+j>i+1) {
j=nxt[j];
}
ans*=(num[j]+1);
ans%=Mod;
}
return ans;
}
signed main () {
// freopen("shell.in","r",stdin);
// freopen("shell.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++) {
cin>>s;
cout<<getnext()<<"\n";
}
return 0;
}
100pts:
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5,Mod=1e9+7;
int n,nxt[N],num[N];
string s;
int getnext () {
memset(nxt,0,sizeof(nxt));
memset(num,0,sizeof(num));
int len = s.size();
nxt[0]=0;
nxt[1]=0;
num[0]=0;
num[1]=1;
int j=0;
for(int i=1;i<len;i++) {
while(j&&s[i]!=s[j]) {
j=nxt[j];
}
if(s[i]==s[j]) j++;
nxt[i+1]=j;
num[i+1]=num[j]+1;
// cout<<i+1<<" : "<<j<<"\n";
}
j=1;int ans=1;
for(int i=1;i<len;i++) {
while(j&&s[i]!=s[j]) {
j=nxt[j];
}
if(s[i]==s[j]) j++;
while(j+j>i+1) {
j=nxt[j];
}
ans*=(num[j]+1);
ans%=Mod;
}
return ans;
}
signed main () {
// freopen("shell.in","r",stdin);
// freopen("shell.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++) {
cin>>s;
cout<<getnext()<<"\n";
}
return 0;
}