POJ 2541 Binary Witch（逆序KMP，好题）

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <string.h>

using namespace std;
const int maxn=1000000+1010;
char s[maxn],str[maxn];
int next[maxn];
char ans[1005];  //答案
int n,l;
int start=1005; //标记字符串的起始位置
int k;

void getNext(char*str) {
    next[1]=0;
    int k=0;
    int lm=strlen(str);
    for(int i=1; i<lm; i++) {
        while(k&&str[k]!=str[i])
            k=next[k];
        if(str[i]==str[k])
            k++;
        next[i+1]=k;
    }
}
//逆序KMP，转化为求最长公共前缀
int kmp(char*P,int len) {
    int k=0,c=0,idx;
    int lm=strlen(P);
    for(int i=start+1; i<start+len; i++) {

        while(k&&P[k]!=str[i])
            k=next[k];
        if(P[k]==str[i])
            k++;
        if(k>c){
            c=k;
            idx=i;
        }
        if(k==lm)
            return i-k;
    }
    if(c)
        return idx-c;
    else
        return -1;
}
int main()
{
    char tmp[20];
    scanf("%d%d",&n,&l);
    scanf("%s",&s);
    int len=strlen(s);
    for(int i=0;s[i];i++){
        str[start+i]=s[len-1-i];
    }
    str[start+len]=‘\0‘;
    int cnt=l,k;
    while(cnt--){
        //截取开始的13个字符
        strncpy(tmp,str+start,13);
        if(len<13)
            tmp[len]=‘\0‘;
        else
            tmp[13]=‘\0‘;
        getNext(tmp);
        k=kmp(tmp,len);
        start--;
        len++;
        if(k==-1)
            str[start]=‘0‘;  //不存在匹配的情况
        else
            str[start]=str[k];
    }
    for(int i=0;i<l;i++)
        ans[i]=str[start+l-1-i];
    ans[l]=‘\0‘;
    printf("%s\n",ans);
    return 0;
}