题意：这个题目好难读懂，，先给你一个字母的转换表，然后给你一个字符串密文+明文，密文一定是全的，但明文不一定是全的，求最短的密文和解密后的明文；
题解：由于密文一定是全的，所以他的长度一定大于整个字符串的一半。将这一半先解密，然后和后缀对比一下，求最长的公共前缀。那么就转换为了拓展kmp问题。
1 #include<bits/stdc++.h>
2 using namespace std;
3
4 const int maxn=100010; //字符串长度最大值
5 int nt[maxn],ex[maxn]; //ex数组即为extend数组
6 char a[maxn],b[maxn],c[maxn];
7 map<char,char> mp;
8
9 //预处理计算next数组
10 void GETNEXT(char *str)
11 {
12 int i=0,j,po,len=strlen(str);
13 nt[0]=len; //初始化nt[0]
14 while(str[i]==str[i+1]&&i+1<len) i++; //计算nt[1]
15 nt[1]=i;
16 po=1; //初始化po的位置
17 for(i=2;i<len;i++){
18 if(nt[i-po]+i<nt[po]+po) nt[i]=nt[i-po]; //第一种情况，可以直接得到nt[i]的值
19 else{ //第二种情况，要继续匹配才能得到nt[i]的值
20 j=nt[po]+po-i;
21 if(j<0) j=0; //如果i>po+nt[po],则要从头开始匹配
22 while(i+j<len&&str[j]==str[j+i]) j++; //计算nt[i]
23 nt[i]=j;
24 po=i; //更新po的位置
25 }
26 }
27 }
28
29 //计算extend数组
30 void EXKMP(char *s1,char *s2)
31 {
32 int i=0,j,po,len=strlen(s1),l2=strlen(s2);
33 GETNEXT(s2); //计算子串的next数组
34 while(s1[i]==s2[i]&&i<l2&&i<len) i++; //计算ex[0]
35 ex[0]=i;
36 po=0; //初始化po的位置
37 for(i=1;i<len;i++){
38 if(nt[i-po]+i<ex[po]+po) ex[i]=nt[i-po]; //第一种情况，直接可以得到ex[i]的值
39 else{ //第二种情况，要继续匹配才能得到ex[i]的值
40 j=ex[po]+po-i;
41 if(j<0) j=0; //如果i>ex[po]+po则要从头开始匹配
42 while(i+j<len&&j<l2&&s1[j+i]==s2[j]) j++; //计算ex[i]
43 ex[i]=j;
44 po=i; //更新po的位置
45 }
46 }
47 }
48
49 int main()
50 {
51 int t;
52 cin>>t;
53 while(t--){
54 cin>>a>>b;
55 int len1=strlen(a);
56 int len2=strlen(b);
57 for(int i=0;i<len1;i++)
58 mp[a[i]]='a'+i;
59 for(int i=0;i<len2;i++)
60 c[i]=mp[b[i]];
61 c[len2]=0;
62 EXKMP(b,c);
63 int k;
64 for(k=0;k<len2;k++)
65 if(k+ex[k]>=len2&&k>=ex[k]) break;
66 for(int i=0;i<k;i++) cout<<b[i];
67 for(int i=0;i<k;i++) cout<<mp[b[i]];
68 cout<<endl;
69 }
70 return 0;
71 }
