Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
52261 | tengzifan | 修复符文 | C++ | 解答错误 | 15 | 28 MS | 2352 KB | 1442 | 2022-07-19 11:51:20 |
#include<bits/stdc++.h> using namespace std; const int maxn=5e5+5; int len,a,b,f[maxn],lenss; bool ans[maxn]; bool vis[maxn]; int main() { //freopen("runes.in","r",stdin); //freopen("runes.out","w",stdout); int T; scanf("%d",&T); while(T--) { string ss,s,t; cin>>ss>>t; s=ss+ss; scanf("%d%d",&a,&b); len=s.size(); for(int i=0;i<len;++i) ans[i] = false; for(int i=0;i<len;++i) vis[i] = false; len=t.size(); for(int i=1;i<len;++i) { int j=f[i-1]; while(j && t[i]!=t[j]) j=f[j-1]; if(t[i] == t[j]) ++j; f[i]=j; } lenss = ss.size(); int j=0; int len1=s.size(); for(int i=0;i<len1;++i) { while(j && s[i] != t[j]) j=f[j-1]; if(s[i] == t[j]) ++j; if(j == len) { ans[i-j+1] = 1; j=f[j-1]; } } //printf("k"); int d=abs(a-b); int now = 1; bool flag=false; while(!vis[now]) { if(ans[now]) { flag=true; printf("yes\n"); break; } vis[now] = 1; if(now+d<lenss) now = now+d; else now = now-lenss-1+d; //printf("%d\n",now); } if(!flag) { for(int i=0;i<len;++i) vis[i] = false; now=1; while(!vis[now]) { if(ans[now]) { flag=true; printf("yes\n"); break; } vis[now] = 1; if(now-d>=0) now = now-d; else now = now+lenss+1-d; } } if(!flag) printf("no\n"); //printf("%d %d %d",ans[0],ans[3],ans[4]); } }