[KMP]ural 1423：String Tale

大致题意：


     “abracadabra” > “aabracadabr” > “raabracadab” > “braabracada” > “abraabracad” > “dabraabraca” > “adabraabrac” > “cadabraabra” > “acadabraabr” > “racadabraab”。


大致思路：
    把第一个字符串复制一份接在自己后面，并将其作为文本串，把第二个字符串作为模式串，做一遍KMP求出模式串在文本串中出现的位置即可。

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=250005;
const int mMax=2000005;
char text[mMax],pat[nMax];
int lent,lenp,nnext[nMax];

void get_nnext(){
    int i,j=-1;
    nnext[0]=-1;
    for(i=1;i<=lenp;i++){     //pat[j]是不是可以理解为i的前一个字符的nnext值所指想的字符
        while(j>-1&&pat[j+1]!=pat[i])j=nnext[j];
        if(pat[j+1]==pat[i])j++;
        nnext[i]=j;
    }
}

int KMP(){
    int ans=0,i=0,j=-1;
    get_nnext();
    for(i=0;i<lent;i++){
        while(j!=-1&&pat[j+1]!=text[i]){
            j=nnext[j];
        }
        if(pat[j+1]==text[i])j=j+1;
        if(j==lenp-1){
      //      cout<<"fuck "<<i<<endl;
            if(i==lenp-1)return 0;
            return lent-i-1;//ans++;  //找到一个匹配
        }
    }
    return -1;
}

int main(){
    int t;
    while(scanf("%d",&lenp)!=EOF){
        scanf("%s%s",text,pat);
        for(int i=0;i<lenp;i++){
            text[i+lenp]=text[i];
        }
        lent=2*lenp;
        text[lent]='\0';
        int ans=KMP();
        if(ans!=-1){
            printf("%d\n",ans);
        }
        else{
            printf("-1\n");
        }
    }
    return 0;
}