HDU 4300(扩展KMP)
Problem Description
Clairewd is a member of FBI. After several years concealing in BUPT, she intercepted some important messages and she was preparing for sending it to ykwd. They had agreed that each letter of these messages would be transfered to another one according to a conversion table.
Unfortunately, GFW(someone’s name, not what you just think about) has detected their action. He also got their conversion table by some unknown methods before. Clairewd was so clever and vigilant that when she realized that somebody was monitoring their action, she just stopped transmitting messages.
But GFW knows that Clairewd would always firstly send the ciphertext and then plaintext(Note that they won’t overlap each other). But he doesn’t know how to separate the text because he has no idea about the whole message. However, he thinks that recovering the shortest possible text is not a hard task for you.
Now GFW will give you the intercepted text and the conversion table. You should help him work out this problem.
第1行仅包含一个整数T（Test Cases），表示测试用例的数量。
每个测试用例包含两行内容。
每个测试用例的第一行为转换表S（String）。其中S[i]表示第i个拉丁字母对应的加密字符。
每个测试用例的第二行为被截获的文本字符串（Ciphertext），其中包含了n个字符需要恢复。
可能该文本已经完整。
For every test case, output a comprehensive and concise piece of text that encompasses all necessary details.
Sample Input
2
abcdefghijklmnopqrstuvwxyz
abcdab
qwertyuiopasdfghjklzxcvbnm
qwertabcdeSample Output
abcdabcd
qwertabcde提供一个密码表之后，在呈现一个密文和一段原始明文（其中原始明文可能不完整）的情况下，请求解如何构造由完整的密文和原始明文组成的字符串使其达到最短。
解题思路在于对密码进行解析以便后续的操作能够保持一致性因此采用扩展KMP算法遍历最长相同前缀从而找到满足条件的最短密钥长度即可
代码：
#pragma GCC optimize(2)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <bitset>
#include <queue>
//#include <random>
#include <time.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ls root<<1
#define rs root<<1|1
const int inf=1ll*1<<60;
const int maxn=2e5+10;
const int maxm=3e6+10;
char arr[maxn],str[maxn],mp[300],op[300];
int to[maxn],extend[maxn];
void getto()
{
to[0]=strlen(arr);
int a=0,p=0;
for(int i=1;arr[i]!='\0';i++){
if(i>=p || i+to[i-a]>=p){
if(i>=p)p=i;
while(arr[i]!='\0' && arr[p]==arr[p-i])p++;
to[i]=p-i;
a=i;
}
else to[i]=to[i-a];
}
}
void getext()
{
int a=0,p=0;
getto();
for(int i=0;str[i]!='\0';i++){
if(i>=p || i+to[i-a]>=p){
if(i>=p)p=i;
while(str[p]!='\0' && str[p]==arr[p-i])p++;
extend[i]=p-i;a=i;
}
else extend[i]=to[i-a];
}
}
signed main()
{
int t;
scanf("%lld",&t);
while(t--){
memset(to,0,sizeof to);
memset(extend,0,sizeof extend);
scanf("%s%s",op,str);
for(int i=0;i<26;i++){
mp[op[i]-'a']=i+'a';
}
memset(arr,0,sizeof arr);
for(int i=0;str[i]!='\0';i++){
arr[i]=mp[str[i]-'a'];
}
//cout<<arr<<endl;
getext();
int ans,len=strlen(str);
ans=len;
for(int i=0;str[i]!='\0';i++){
if(i>=extend[i] && i+extend[i]>=len){
ans=i;
break;
}
}
//cout<<ans<<endl;
for(int i=0;i<ans;i++){
printf("%c",str[i]);
}
for(int i=0;i<ans;i++){
printf("%c",mp[str[i]-'a']);
}
puts("");
}
}