AC代码:
#include<bits/stdc++.h>
using namespace std;
#define N 1000010
#define mod 1000000007
#define R register
#define int long long
#define pow _Pow
#define pow2(_) (1<<(_))
#define max(_a,_b) (((_a)>(_b))?(_a):(_b))
#define min(_a,_b) (((_a)>(_b))?(_b):(_a))
#define Fl(_1,_2,_3,_4) for(R int _1=(_2);(_1)<=(_3);(_1)+=(_4))
#define Fr(_1,_2,_3,_4) for(R int _1=(_2);(_1)>=(_3);(_1)-=(_4))
#define getchar() (strto1==strto2&&(strto2=(strto1=fsr)+fread(fsr,1,1<<15,stdin),strto1==strto2)?EOF:*strto1++)
char fsr[1<<15],*strto1=fsr,*strto2=fsr;
inline int read()
{
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return s*w;
}
inline void write(int x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
}
inline int _Pow(int a,int b)
{
#define Mod 100000007
int ans=1;
while(b)ans=(b&1)?(ans*a%Mod):ans,a=a%Mod*a%Mod,b=b>>1;
return ans%Mod;
#undef Mod
}
int T;
int Next[N];
string ans;
string a;
signed main()
{
ios::sync_with_stdio(false);
cin>>T>>ans;T--;
while(T--)
{
int n;
cin>>a,n=min(a.size(),ans.size());
string b=a+"###################IloveI_Eforever##################"+ans.substr(ans.size()-n,n);b=" "+b;
Next[0]=Next[1]=0;
for(R int i=2,j=0;i<=b.size();i++)
{
while(j&&b[i]!=b[j+1])j=Next[j];
if(b[i]==b[j+1])j++;
Next[i]=j;
}
Fl(i,Next[b.size()-1],a.size()-1,1)
ans+=a[i];
}
cout<<ans<<endl;
return 0;
}
WA代码:
#include<bits/stdc++.h>
using namespace std;
#define N 1000010
#define mod 1000000007
#define R register
#define int long long
#define pow _Pow
#define pow2(_) (1<<(_))
#define max(_a,_b) (((_a)>(_b))?(_a):(_b))
#define min(_a,_b) (((_a)>(_b))?(_b):(_a))
#define Fl(_1,_2,_3,_4) for(R int _1=(_2);(_1)<=(_3);(_1)+=(_4))
#define Fr(_1,_2,_3,_4) for(R int _1=(_2);(_1)>=(_3);(_1)-=(_4))
#define getchar() (strto1==strto2&&(strto2=(strto1=fsr)+fread(fsr,1,1<<15,stdin),strto1==strto2)?EOF:*strto1++)
char fsr[1<<15],*strto1=fsr,*strto2=fsr;
inline int read()
{
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return s*w;
}
inline void write(int x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
}
inline int _Pow(int a,int b)
{
#define Mod 100000007
int ans=1;
while(b)ans=(b&1)?(ans*a%Mod):ans,a=a%Mod*a%Mod,b=b>>1;
return ans%Mod;
#undef Mod
}
int T;
int Next[N];
string ans;
string a;
signed main()
{
ios::sync_with_stdio(false);
cin>>T>>ans;T--;
while(T--)
{
int n;
cin>>a,n=min(a.size(),ans.size());
string b=a+"###I love I_E forever###"+ans.substr(ans.size()-n,n);b=" "+b;
Next[0]=Next[1]=0;
for(R int i=2,j=0;i<=b.size();i++)
{
while(j&&b[i]!=b[j+1])j=Next[j];
if(b[i]==b[j+1])j++;
Next[i]=j;
}
Fl(i,Next[b.size()-1],a.size()-1,1)
ans+=a[i];
}
cout<<ans<<endl;
return 0;
}
两份代码中,只有第48行中:
"###################IloveI_Eforever##################"(AC的)
"###I love I_E forever###"(WA的)
区别仅在字符串长度的区别,请问是什么根本原因造成的WA