雪姐无敌～

 

这题传说是一个扩展KMP的应用，不过我不会exKMP，只好先用KMP乱搞一下了。

KMP我TMD也不会啊。。。这题就当加深理解了。。

 

我们将原串称为MIA，将解密后的串称为STR

我们要找到的的是MIA的后辍与STR的前辍的最长的交。

 

解题的方法就是以MIA为母串，以STR为模式串，做一次KMP匹配。从而求得当母串完全匹配之后，模式串的匹配位置。

 

如M:abcdab T:abcdab (样例，没有加密）

最后的匹配位置就是ab < ...

所以M的前4个是加密串，后4个可以由前4个解密得到。

 

但是，有特殊情况是abababa这样的。

匹配位置是len，而题目中给出的信息是M[0...n-1]+S[0...m]   (0<=m<len)

所以我们所要的结果就是next[ptr]。

再加上要求最短的信息串，则如果ptr>len/2，则ptr=next[ptr]，这样就可以得到最后的结果。

 

学艺不精，语文不好，说错了不怪我。大家参考着看呗～～

 

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 10 using namespace std;11 12 #define print(x) cout<
              
               <
               
                >x14 15 const int SIZE=100000;16 17 int next[SIZE+5];18 char conv[32],anti[32];19 char str[SIZE+5],mia[SIZE+5];20 int len;21 22 void kmp_get_next()23 {24 next[0]=-1;25 for(int i=0,j=-1;i
                
                 =0 and str[i]!=str[j]) j=next[j];28 }29 }30 31 char decode(char x)32 {33 return conv[x-'a'];34 }35 36 void make_anti()37 {38 for(int i=0;conv[i];i++)39 {40 anti[conv[i]-'a']='a'+i;41 }42 }43 44 char encode(char x)45 {46 return anti[x-'a'];47 }48 49 int slove()50 {51 int i,j;52 i=j=0;53 while(i
                 
                  len/2) j=next[j];65 return j;66 }67 68 int main()69 {70 int T;71 input(T);72 while(T--)73 {74 memset(mia,0,sizeof(mia));75 memset(str,0,sizeof(str));76 memset(next,0,sizeof(next));77 scanf("%s",conv);78 scanf("%s",str);79 len=strlen(str);80 for(int i=0;str[i];i++)81 {82 mia[i]=decode(str[i]);83 }84 make_anti();85 kmp_get_next();86 int k=slove();87 for(int i=0;mia[i+k];i++)88 {89 printf("%c",str[i]);90 }91 for(int i=0;mia[i+k];i++)92 {93 printf("%c",encode(str[i]));94 }95 puts("");96 }97 return 0;98 }