题意非常难懂：

大概是给你一个密码表，一个劫获的串。那个劫获的串的前一部分是密文后一部分是明文，但是不清楚分界线在哪里。让你把这个串补完，并使长度尽量小。。。

思路：把劫获的串整个翻译成密码串作为文本串T，原来串P作为模板串做EXKMP，从中间位置开始枚举，如果在位置i上的ex[ i ]等于i到结尾的距离，分界线就在这了。。。

Clairewd’s message

2
abcdefghijklmnopqrstuvwxyz
abcdab
qwertyuiopasdfghjklzxcvbnm
qwertabcde

abcdabcd
qwertabcde

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn=110000;

char T[maxn],P[maxn],table[maxn],Table[maxn];
int next[maxn],ex[maxn];

void pre_exkmp(char P[])
{
    int m=strlen(P);
    next[0]=m;
    int j=0,k=1;
    while(j+1<m&&P[j]==P[j+1]) j++;
    next[1]=j;
    for(int i=2;i<m;i++)
    {
        int p=next[k]+k-1;
        int L=next[i-k];
        if(i+L<p+1) next[i]=L;
        else
        {
            j=max(0,p-i+1);
            while(i+j<m&&P[i+j]==P[j]) j++;
            next[i]=j; k=i;
        }
    }
}

void exkmp(char P[],char T[])
{
    int m=strlen(P),n=strlen(T);
    pre_exkmp(P);
    int j=0,k=0;
    while(j<n&&j<m&&P[j]==T[j]) j++;
    ex[0]=j;
    for(int i=1;i<n;i++)
    {
        int p=ex[k]+k-1;
        int L=next[i-k];
        if(i+L<p+1) ex[i]=L;
        else
        {
            j=max(0,p-i+1);
            while(i+j<n&&j<m&&T[i+j]==P[j]) j++;
            ex[i]=j; k=i;
        }
    }
}

int main()
{
    int T_T;
    scanf("%d",&T_T);
while(T_T--)
{
    scanf("%s%s",Table,P);
    for(int i=0;i<26;i++)
    {
        table[Table[i]-‘a‘]=‘a‘+i;
    }
    memset(T,0,sizeof(T));
    int n=strlen(P);
    for(int i=0;i<n;i++) T[i]=Table[P[i]-‘a‘];
    exkmp(P,T);
    int pos=n;
    for(int i=n-n/2;i<n;i++)
    {
        if(ex[i]>=n-i)
        {
            pos=i; break;
        }
    }
    for(int i=0;i<pos;i++) putchar(P[i]);
    for(int i=0;i<pos;i++) putchar(table[P[i]-‘a‘]);
    putchar(10);
}
    return 0;
}

HDOJ 4300 Clairewd’s message,布布扣,bubuko.com

HDOJ 4300 Clairewd’s message

原文：http://blog.csdn.net/u012797220/article/details/22695193