HDU 4300 Clairewd’s message KMP

제목 주소: http://acm.hdu.edu.cn/showproblem.php?pid=4300
이 문제 의 제 의 는 너무 이해 하기 어렵다.
첫 번 째 줄 에서 26 자 모 를 주 는 비밀문 입 니 다.대응 명문 은 a-z 입 니 다.
두 번 째 줄 은 당신 에 게 앞 에는 비밀문 이 있 고 뒤 에는 명문 의 문자열 이 있 습 니 다.비밀문 은 반드시 완전 할 것 입 니 다.그러나 명문 은 없 을 수도 있 고 다 있 을 수도 있 습 니 다.
가장 짧 은 밀 문+명문 을 구하 라 고.
abcdab
최 단 비밀문서:abcd,대응 하 는 명문 은 abcd 입 니 다.
그래서 최 단 비밀문서+명문 abcdabcd
예 2:qwertabcde
최 단 비밀문서:qwert,대응 하 는 명문 은 abcde 입 니 다.
그래서 최 단 밀 문+명문 은 qwertabcde
이해 가 안 돼.
사고:명문 의 길 이 는 반드시 len/2 보다 작 을 것 이다.그리고 뒤의 절반 으로 대응 하 는 명문 과 일치 할 것 이다.
예 를 들 어 첫 번 째 예:dab 와 abcdab 의 최대 일치 가 t=2 인 것 은 두 개가 명문 이 고 t 에서 len-t 출력 뒤에 있 는 것 은 표시 되 지 않 은 명문 임 을 나타 낸다.
AC 코드:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
using namespace std;

typedef __int64 LL;
const int N=100090;
const LL II=1000000007;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);

char word[N],yi[26],mi[26],xh[N];
int wlen,next[N];

void getnext(char *p)
{
    int j=0,k=-1;
    next[0]=-1;
    while(j<wlen)
    {
        if(k==-1||p[j]==p[k])
        {
            j++;    k++;
            next[j]=k;
        }
        else
            k=next[k];
    }
}

int kmp(char *text,char *word)
{
    int i=0,j=0,tlen=strlen(text);
    while(i<tlen)
    {
        if(j==-1||text[i]==word[j])
            j++,i++;
        else
            j=next[j];
    }
    return j;//                    
}

int main()
{
    int i,j,T;
    scanf("%d",&T);
	while(T--)
	{
	    scanf("%s%s",yi,word);
	    printf("%s",word);
	    for(i=0;i<26;i++)
            mi[yi[i]-'a']=i+'a';//       
        wlen=strlen(word);
        strcpy(xh,word+(wlen+1)/2);
        for(i=0;i<wlen;i++)
            word[i]=mi[word[i]-'a'];
        getnext(word);
        int t=kmp(xh,word);//       
        int p=wlen-t;//     
        word[p]='\0';
        printf("%s
",word+t);// t p
	}
	return 0;
}