HDOJnbsp;nbsp;4300nbsp;nbsp;nbsp;Clairewd’snbsp;message

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

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int L=100010;
char a[100],b[100];
char str[L],pat[L];
int fail[L];
int kmp(int n)
{
    int i,j,k;
    memset(fail,-1,sizeof(fail));
    for (i=1; pat[i]; ++i)
    {
        for (k=fail[i-1]; k>=0 && pat[i]!=pat[k+1]; k=fail[k]);
        if  (pat[k+1]==pat[i]) fail[i]=k+1;
    }
    i=j=0;
    while (str[i])
    {
        if (pat[j]==str[i]) ++i,++j;
        else if (j==0) ++i;
        else j=fail[j-1]+1;
    }
    if (j==0) return -1; else j--;
    while ((j+1)*2>n) j=fail[j];
    return j;
}
int main()
{
    int o,i,n,k;
    scanf("%d",&o);
    while (o--)
    {
        scanf("%s",a);
        for (i=0; i<26; i++) b[a[i]-'a']=i+'a';
        scanf("%s",str);
        for (i=0; str[i]; i++) pat[i]=b[str[i]-'a'];
        n=strlen(str); pat[n]='\0';
        k=kmp(n);
        for (i=0; i<n-k-1; i++) printf("%c",str[i]);
        for (i=0; i<n-k-1; i++) printf("%c",pat[i]);
        printf("\n");
    }
}