提交时间:2022-07-19 11:51:31

运行 ID: 52276

#include<cstdio> #include<cstring> using namespace std; typedef long long ll; const ll mod=1e9+7; int T; char s[500005],r[500005]; ll fac[500005]; int a,b; int main(){ fac[0]=1ll; for(int i=1;i<=500000;++i) fac[i]=fac[i-1]*27ll%mod; scanf("%d",&T); while(T--){ scanf("%s%s%d%d",s,r,&a,&b); if(a>b){ int t=a; a=b; b=t; } int n=strlen(s); for(int i=n;i<n+n-1;++i) r[i]=r[i-n]; ll ha=0,hb; for(int i=0;i<a;++i) ha=ha*27ll+(s[i]-'a'+1),ha%=mod; hb=ha; for(int i=a;i<b;++i) hb=hb*27ll+(s[i]-'a'+1),hb%=mod; ll ra=0,rb=0; for(int i=n-1;i>=b;--i) rb=(rb*27ll+(s[i]-'a'+1))%mod; ra=rb; for(int i=b-1;i>=a;--i) ra=(ra*27ll+(s[i]-'a'+1))%mod; ll hr=0,hr1=0,hr2=0,hr3=0,hr4=0; bool f1=0,f2=0,f3=0,f4=0; for(int i=0;i<n+n-1;++i){ hr=(hr*27ll+(r[i]-'a'+1))%mod; if(i-a>=0) hr1=(hr1*27ll+(r[i-a]-'a'+1))%mod; if(i-b>=0) hr2=(hr2*27ll+(r[i-b]-'a'+1))%mod; if((hr-hr1*fac[a]%mod+mod)%mod==ha) f1=1; if((hr-hr2*fac[b]%mod+mod)%mod==hb) f2=1; } hr=0; for(int i=n+n-2;i>=0;--i){ hr=(hr*27ll+(r[i]-'a'+1))%mod; if(i+n-a<=n+n-2) hr3=(hr3*27ll+(r[i+n-a]-'a'+1))%mod; if(i+n-b<=n+n-2) hr4=(hr4*27ll+(r[i+n-b]-'a'+1))%mod; if((hr-hr3*fac[n-a]%mod+mod)%mod==ra) f3=1; if((hr-hr4*fac[n-b]%mod+mod)%mod==rb) f4=1; } if(f1&&f2&&f3&&f4) puts("yes"); else puts("no"); } return 0; }