题意:
判断P串是不是能和T串循环移位K位后的字符串有匹配点
分析:
把T往自身后面贴一下变成TT,然后看P在TT中有没有匹配点即可~~~
这种往后帖一下的思想可以说是一种技巧,比如:求数组挖去连续一块后求剩下的有多少个不同的数.
#include<bits/stdc++.h>using namespace std;const int maxn = 100000+111;
char s[maxn+maxn],p[maxn];
int n,m,f[maxn];void getfail()
{f[0]=f[1]=0;for(int i=1;i<m;i++){int j=f[i];while(j && p[j]!=p[i])j=f[j];f[i+1]=p[i]==p[j]?j+1:0;}
}
bool kmp()
{if(n<m)return false;int j=0;for(int i=0;i<n+n;i++){while(j && s[i]!=p[j])j=f[j];if(s[i]==p[j])j++;if(j==m)return true;}return false;
}int main()
{while(scanf("%s%s",s,p)!=EOF){n=strlen(s);m=strlen(p);for(int i=n;i<2*n;i++){s[i]=s[i-n];}s[2*n]=0;if(kmp())puts("yes");else puts("no");}
}