Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
52333 | lzqy_ | 修复符文 | C++ | 解答错误 | 10 | 29 MS | 3004 KB | 2160 | 2022-07-19 11:53:31 |
#include<bits/stdc++.h> using namespace std; const int mod1=1e9+7; const int base1=37; const int mod2=998244353; const int base2=31; const int maxn=500010; char a[maxn<<1],b[maxn],c[maxn]; int Ha1[maxn],Hb1[maxn],Pow1[maxn]; int Ha2[maxn],Hb2[maxn],Pow2[maxn]; int T,l1,l2,n; int Hash1_a(int l,int r){ if(l>r) return 0; return (Ha1[r]-Pow1[r-l+1]*1ll*Ha1[l-1]%mod1+mod1)%mod1; } int Hash2_a(int l,int r){ if(l>r) return 0; return (Ha2[r]-Pow2[r-l+1]*1ll*Ha2[l-1]%mod2+mod2)%mod2; } int Hash1_b(int l,int r){ if(l>r) return 0; return (Hb1[r]-Pow1[r-l+1]*1ll*Hb1[l-1]%mod1+mod1)%mod1; } int Hash2_b(int l,int r){ if(l>r) return 0; return (Hb2[r]-Pow2[r-l+1]*1ll*Hb2[l-1]%mod2+mod2)%mod2; } bool chk(){ int x=-1; for(int i=1;i<=n;i++) if(Hash1_a(1,n-i)==Hash1_b(1+i,n)&&Hash2_a(1,n-i)==Hash2_b(1+i,n)) if(Hash1_a(n-i+1,n)==Hash1_b(1,i)&&Hash2_a(n-i+1,n)==Hash2_b(1,i)) {x=i;break;} if(~x){ if(!x) return printf("yes\n"),1; for(int i=1,sum1=0,sum2=0;i<=n;i++) if((sum1+=l2-l1)==x) return printf("yes\n"),1; else if((sum2+=n-l2+l1)==x) return printf("yes\n"),1; } return 0; } void Reverse(int x){ for(int i=n;i;i--) swap(a[i],a[i+x]); for(int i=n-x+1;i<=n;i++) swap(a[i-n+x],a[i]); } int main(){ scanf("%d",&T); while(T--){ scanf("%s%s",a+1,b+1); scanf("%d%d",&l1,&l2); if(l1>l2) swap(l1,l2); n=strlen(a+1),Pow1[0]=Pow2[0]=1; for(int i=1;i<=n;c[i]=a[i],i++){ Ha1[i]=(Ha1[i-1]*1ll*base1+a[i]-'a')%mod1; Ha2[i]=(Ha2[i-1]*1ll*base2+a[i]-'a')%mod2; Hb1[i]=(Hb1[i-1]*1ll*base1+b[i]-'a')%mod1; Hb2[i]=(Hb2[i-1]*1ll*base2+b[i]-'a')%mod2; Pow1[i]=Pow1[i-1]*1ll*base1%mod1; Pow2[i]=Pow2[i-1]*1ll*base2%mod2; } if(chk()) continue; Reverse(l1); for(int i=1;i<=n;i++){ Ha1[i]=(Ha1[i-1]*1ll*base1+a[i]-'a')%mod1; Ha2[i]=(Ha2[i-1]*1ll*base2+a[i]-'a')%mod2; } if(chk()) continue; for(int i=1;i<=n;i++) a[i]=c[i]; Reverse(l2); for(int i=1;i<=n;i++){ Ha1[i]=(Ha1[i-1]*1ll*base1+a[i]-'a')%mod1; Ha2[i]=(Ha2[i-1]*1ll*base2+a[i]-'a')%mod2; } if(chk()) continue; printf("no\n"); } return 0; }