HDU 2203 亲和串 (KMP)

最近看了看KMP算法，发现其状态转移图构造的十分巧妙，通过递推计算出返回的地方，以降低时间复杂度。    该题就是一个KMP裸题，不过该题可以循环 移位，那么不妨我们将s1扩充成原来的两倍就行了，但是这样要实现判断两个串的大小，不然扩充后的s1有可能匹配上一个比它长的s2 。

细节参见代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
using namespace std;
const int maxn = 100000 + 5;
int T,n,m,f[maxn];
char s1[2*maxn],s2[maxn];
void getFail(char* P, int* f) {
    int m = strlen(P);
    f[0] = 0; f[1] = 0;
    for(int i = 1; i < m; i++) {
        int j = f[i];
        while(j && P[i]!=P[j]) j = f[j];
        f[i+1] = P[i] == P[j] ? j+1 : 0;
    }
}
bool findd(char* T, char* P, int* f) {
    int n = strlen(T), m = strlen(P);
    int nn = n;
    for(int i=0;i<n;i++)
        T[nn++] = T[i];
    n = nn;
    getFail(P, f);
    int j = 0;
    bool ok = false;
    for(int i=0;i<n;i++) {
        while(j && P[j]!=T[i]) j = f[j];
        if(P[j] == T[i]) j++;
        if(j == m) { ok = true; break; }
    }
    return ok;
}
int main() {
    while(~scanf("%s",s1)) {
        scanf("%s",s2);
        if(strlen(s1) < strlen(s2)) printf("no\n");
        else if(findd(s1,s2,f)) printf("yes\n");
        else printf("no\n");
    }
    return 0;
}