题目链接：https://vjudge.net/problem/HDU-4300
这道题理解了题意就容易想思路了，我看了别人的题解才理解了题意：
题目大意：
发送一个密文，为字符串S。这段密文的前半部份是加密过的，后半部分是没有加密过的。现在这段密文被截获，但是密文的尾部的一部份损失了。例如，假设密文是xxxxzzzz, xxxx是加密过的，zzzz是没加密的，因为损失了后面一部份，所以截获的内容可能为xxxxzz， 可以保证截获的内容的无加密内容一定是完整的。
给出密码表，这个密码表为一串26个字母的字符串，a[0]表示a加密后的字母，a[1]表示b加密后的字母....a[25]表示z加密后的字母。
要你恢复到无损坏的密文。在截获的内容中，要让明文最短。
所以可以使用扩展KMP算法
先将字符串S当做密文转换生成明文T
然后S是文本串，T是模式串，求T与S后缀的匹配，从S中间开始，找到最短的匹配
具体看代码
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N=1e5+10; const int M=1e5+10; char a[N],b[M],c[26],c0[26]; int next0[M],extend[N]; void get_next() { int len=strlen(b); next0[0]=len; int i=0; while(i<len-1&&b[i]==b[i+1]) ++i; next0[1]=i; i=1; for(int k=2;k<len;++k) { int p=i+next0[i]-1; int L=next0[k-i]; if(k-1+L>=p) { int j=(p-k+1)>0?(p-k+1):0; while(k+j<len&&b[k+j]==b[j]) ++j; next0[k]=j; i=k; } else next0[k]=L; } } void get_extend() { int i=0,j,po,alen=strlen(a),blen=strlen(b); get_next(); while(a[i]==b[i]&&i<alen&&i<blen) i++; extend[0]=i; po=0; for(i=1;i<alen;i++) { if(next0[i-po]+i<extend[po]+po) extend[i]=next0[i-po]; else { j=extend[po]+po-i; if(j<0) j=0; while(i+j<alen&&j<blen&&a[j+i]==b[j]) j++; extend[i]=j; po=i; } } } int main() { int T; scanf("%d",&T); while(T--) { scanf("%s",c); for(int i=0;i<26;i++) c0[c[i]-'a']='a'+i; scanf("%s",a); int alen=strlen(a); for(int i=0;i<alen;i++) b[i]=c0[a[i]-'a']; b[alen]='\0'; get_extend(); int s=alen/2; if(alen%2) s++; //这里要注意，输出文本长度必须大于等于输入文本 for(int i=s;i<=alen;i++) //原来是i<alen，没考虑无匹配情况，WA了 if(extend[i]==alen-i) { for(int j=0;j<i;j++) printf("%c",a[j]); for(int j=0;j<i;j++) printf("%c",c0[a[j]-'a']); printf("\n"); break; } } return 0; }
