提交时间:2022-07-19 16:54:47
运行 ID: 52634
#include <bits/stdc++.h> using namespace std; int t,a,b,n,gcd,hash1[500010],hash2[500010],k[500010]; char ch1[500010],ch2[500010]; bool flag; int Gcd(int x,int y) { return !y ? x : Gcd(y,x % y); } int ha1(int x,int y) { return hash1[y] - hash1[x - 1] * k[y - x + 1]; } int ha2(int x,int y) { return hash2[y] - hash2[x - 1] * k[y - x + 1]; } int main() { k[0] = 1,k[1] = 114514; for(int i = 2; i <= 5e5; i++) k[i] = k[i - 1] * k[1]; scanf("%d",&t); while(t--) { scanf("%s%s",ch1 + 1,ch2 + 1); scanf("%d%d",&a,&b); n = strlen(ch1 + 1); if(a > b) swap(a,b); gcd = Gcd(b - a,n); flag = false; for(int i = 1; i <= n; i++) { hash1[i] = hash1[i - 1] * k[1] + ch1[i]; hash2[i] = hash2[i - 1] * k[1] + ch2[i]; } for(int i = 0; i < n; i++) { if(i % gcd) continue; if(ha1(i + 1,n) == ha2(1,n - i) && ha1(1,i) == ha2(n - i + 1,n)) { flag = true; break; } } if(flag) { printf("yes\n"); continue; } reverse(ch1 + 1,ch1 + a + 1); reverse(ch1 + a + 1,ch1 + n + 1); for(int i = 1; i <= n; i++) hash1[i] = hash1[i - 1] * k[1] + ch1[i]; for(int i = 0; i < n; i++) { if(i % gcd) continue; if(ha1(i + 1,n) == ha2(1,n - i) && ha1(1,i) == ha2(n - i + 1,n)) { flag = true; break; } } if(flag) printf("yes\n"); else printf("no\n"); } return 0; }