HDU - 2203 亲和串(Kmp)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2203

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;
/*************************************************************************************************************
        不知道什么原因 wa 了一下午，最后换了个模板 AC 了，以后就用这个模板，忘记之前的模板吧。
        值得注意一点的是输入：
        1，C++果断 tel; 所以采用 C 的输入。
        2，别一次两个字符串都输入，先输入一个到 EOF，在输入另一个，亲测如果同时输入会超时
*************************************************************************************************************/

int Next[100005];
char s[100005*2],p[100005];

void getNext(int m){
    int i=0,j=-1;
    Next[0]=-1;

    while(i < m){
        if(j == -1 || p[i] == p[j])
            Next[++i] = ++j;
        else
            j=Next[j];
    }
}

bool Kmp(int n,int m){
    getNext(m);
    int i = 0,j = 0;
    while(i < n && j < m){
        if(j == -1 || s[i] == p[j]){
            i++;
            j++;
        }
        else
            j=Next[j];
    }
    if(j >= m)  return true;
    else
        return false;
}

int main()
{
    while(scanf("%s",&s) != EOF){
        scanf("%s",&p);
        int lt1=strlen(s),lt2=strlen(p);
        if(lt1 < lt2) { cout<<"no"<<endl; continue;}

        strncpy(s+lt1,s,lt1);
        if(Kmp(lt1*2,lt2))
            cout<<"yes"<<endl;
        else
            cout<<"no"<<endl;
    }
    return 0;
}