2 abcdefghijklmnopqrstuvwxyz abcdab qwertyuiopasdfghjklzxcvbnm qwertabcde
abcdabcd qwertabcde
题意好难理解啊
先给你个table,也就是明文对应的暗文
再给你一个串, 里面是暗文+明文,明文不一定完整,甚至没有
让你以最短的形式补全这个串,前半部分为暗文,后半部分为对应的明文
先把串的明文找出来,以此为模式串,原串为主串,进行扩展kmp,然后遍历,发现i + extend[i] >= len 的话就找到答案了,如果找不到就输出主串和模式串
/*************************************************************************
> File Name: hdu4300.cpp
> Author: ALex
> Mail: zchao1995@gmail.com
> Created Time: 2015年01月30日 星期五 21时09分35秒
************************************************************************/
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const double pi = acos(-1);
const int inf = 0x3f3f3f3f;
const double eps = 1e-15;
typedef long long LL;
typedef pair <int, int> PLL;
const int N = 100010;
char T[N];
char S[N];
int next[N];
int extend[N];
char table[30];
char rtable[30];
void EXTEND_KMP ()
{
int lens = strlen (S);
int lent = strlen (T);
next[0] = lent;
int i, j, p, L;
j = 0;
while (j + 1 < lent && T[j] == T[j + 1])
{
++j;
}
next[1] = j;
int a = 1;
for (i = 2; i < lent; ++i)
{
p = next[a] + a - 1;
L = next[i - a];
if (i + L < p + 1)
{
next[i] = L;
}
else
{
j = max(0, p - i + 1);
while (i + j < lent && T[i + j] == T[j])
{
++j;
}
next[i] = j;
a = i;
}
}
j = 0;
while (j < lens && S[j] == T[j])
{
++j;
}
extend[0] = j;
a = 0;
for (i = 1; i < lens; ++i)
{
p = extend[a] + a - 1;
L = next[i - a];
if (L + i < p + 1)
{
extend[i] = L;
}
else
{
j = max(0, p - i + 1);
while (i + j < lens && j < lent && S[i + j] == T[j])
{
++j;
}
extend[i] = j;
a = i;
}
}
}
int main ()
{
int t;
scanf("%d", &t);
while (t--)
{
scanf("%s", table);
scanf("%s", S);
int len = strlen (S);
for (int i = 0; i < 26; ++i)
{
rtable[table[i] - 'a'] = 'a' + i;
}
for (int i = 0; i < len; ++i)
{
T[i] = rtable[S[i] - 'a'];
}
T[len] = '\0';
EXTEND_KMP ();
bool flag = false;
int e;
int mid = len / 2 + (len % 2 ? 1 : 0);
for (int i = 0; i < len; ++i)
{
if (extend[i] + i >= len && i >= mid)
{
e = i;
flag = true;
break;
}
}
if (!flag)
{
printf("%s%s\n", S, T);
continue;
}
for (int i = 0; i < e; ++i)
{
printf("%c", S[i]);
}
for (int i = 0; i < e; ++i)
{
printf("%c", T[i]);
}
printf("\n");
}
return 0;
}原文：http://blog.csdn.net/guard_mine/article/details/43316545