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

2

abcdefghijklmnopqrstuvwxyz

abcdab

qwertyuiopasdfghjklzxcvbnm

qwertabcde

abcdabcd

qwertabcde

题意：

比較难理解,给定两组字符串,第一组仅仅有26个字符表相应明文中a,b,c,d....z能够转换第1个,第2个...第26个字符变成密文,

第二组字符串是给定的密文+明文,明文可能不完整(缺失或没有),叫你补充完整整个密文+明文是最短的；

PS:读了好几遍都不理解题意。用了翻译工具还是不能理解。最后还是百度了才知道题意！（毕竟英语太渣）。

思路：

把给出的不完整的明文加密文字符串所有转换一次。将转换后的做模式串，与原串进行kmp，记录返回的j值（j值代表的就是前缀和后缀的最长相等长度）。然后再与给出的明文加密文字符串比較一下。

代码例如以下：

//#pragma warning (disable:4786)

#include <cstdio>

#include <cmath>

#include <cstring>

#include <string>

#include <cstdlib>

#include <climits>

#include <ctype.h>

#include <queue>

#include <stack>

#include <vector>

#include <utility>

#include <deque>

#include <set>

#include <map>

#include <iostream>

#include <algorithm>

using namespace std;

const double eps=1e-9;

const double pi=3.1415926535897932384626;

#define INF 1e18

//typedef long long LL;

//typedef __int64 LL;

const int MAXN = 100017;

char strm[MAXN];//password表

char strz[MAXN];//不完整的密文和密文

char str[MAXN]; //password表转换后

char s[MAXN];   //密文和明文转换后

int next[MAXN];

void getnext( char T[], int len)

{

    int i = 0, j = -1;

    next[0] = -1;

    while(i < len)

    {

        if(j == -1 || T[i] == T[j])

        {

            i++, j++;

            next[i] = j;

        }

        else

            j = next[j];

    }

}

int KMP(int len1, int len2)

{

    int i, j = 0;

    if(len1%2 == 1)

    {

        i = len1/2+1;

    }

    else

        i = len1/2;

    while(i < len1 && j < len2)

    {

        if(j == -1 || strz[i] == s[j])

        {

            i++, j++;

        }

        else

            j = next[j];

    }

    return j;//j值代表的就是前缀和后缀的最长相等长度

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%s",strm);

        for(int i = 0; i < 26; i++)

        {

            char ss = strm[i];

            str[ss] = i;

        }

        scanf("%s",strz);

        int lenz = strlen(strz);

        for(int i = 0; i < lenz; i++)//将密文和明文依照password表转换

        {

            int tt = str[strz[i]];

            s[i] = 'a' + tt;

        }

        int lens = strlen(s);

        getnext(s, lens);

        int j = KMP(lenz, lens);//得到密文的个数

        if(j*2 == lenz)//前缀和后缀恰各占一半

        {

            printf("%s\n",strz);

        }

        else

        {

            int tt = lenz - j;

            printf("%s",strz);

            for(int i = j; i < tt; i++)//须要加入的明文

            {

                printf("%c",s[i]);

            }

            printf("\n");

        }

    }

    return 0;

}