本文共 1632 字，大约阅读时间需要 5 分钟。

链接：

题目大意：

发送一个密文，为字符串S。这段密文的前半部份是加密过的，后半部分是没有加密过的。现在这段密文被截获，但是密文的尾部的一部份损失了。例如，假设密文是xxxxzzzz, xxxx是加密过的，zzzz是没加密的，因为损失了后面一部份，所以截获的内容可能为xxxxzz， 可以保证截获的内容的无加密内容一定是完整的。

给出密码表，这个密码表为一串26个字母的字符串，a[0]表示a加密后的字母，a[1]表示b加密后的字母....a[25]表示z加密后的字母。

要你恢复到无损坏的密文。在截获的内容中，要让明文最短。

分析与总结：

先来看看暴力的方法是怎样的。直接从S的一半位置开始枚举，然后判断后面部分的经过加密后是否都和明文部分相匹配即可。

事实证明，数据弱了，可以暴力水过。

如果不水，这题的正解应该是用拓展KMP（）

先把S全部都当作是密文的，然后把S全转换成明文，保存为T

这时，S中的密文部分就全部都变成了明文，而明文部分都变成了xxx（不用管是什么）。

然后可以发现，原来的S中的明文部分是S的后缀，而T中的明文部分是T的前缀。

所以，演变成了求S【i....n】中的与T的最长公共前缀，就是赤裸的拓展KMP问题了。

代码：

1. 暴力

#include
   
    #include
    
     #include
     
      using namespace std;const int MAXN = 1000005;char a[50];char b[MAXN];char str[MAXN];int  f[MAXN];int  val[200];int main(){    int nCase;    scanf("%d",&nCase);    while(nCase--){        scanf("%s %s",a,b);        for(int i=0; a[i]; ++i){            val[a[i]] = i+'a';        }        int len=strlen(b);        int mid;        if(len & 1) mid=len/2;        else mid=len/2-1;        int pos;        for(int i=mid; i
     
    
   

2. 拓展KMP

#include
   
    #include
    
     #include
     
      using namespace std;typedef long long int64;const int MAXN = 1000005;char a[50];char b[MAXN];char str[MAXN];int  next[MAXN];int  extend[MAXN];int  hash[200];void getNext(const char *T){    int len=strlen(T), a=0;    next[0] = len;    while(a
      
       = p){            int j = (p-k+1)>0?(p-k+1):0;            while(k+j
       
        = p){            int j=max(p-k+1, 0);            while(k+j
        
         =len && i>=extend[i]){ maxi=i; break; } } memset(str, 0, sizeof(str)); for(int i=0; i
        
       
      
     
    
   

          原创  ， By   D_Double  (转载请标明)