昨晚一不小心学了拓展KMP,被虐了一晚，最终是这份资料救了我…
说得简单易懂。
然后学了kuangbin的模版：
/* * 扩展KMP算法 *///next[i]:x[i…m-1]与x[0…m-1]的最长公共前缀//extend[i]:y[i…n-1]与x[0…m-1]的最长公共前缀void pre_EKMP(char x[],int m,int next[]) //x串的自身EKMP{next[0]=m; //显然int j=0;while(j+1<m && x[j]==x[j+1]) j++;next[1]=j; //就这里和EKMP有点区别，EKMP不需初始化next[1]int k=1;for(int i=2;i<m;i++){int p=next[k]+k-1;int L=next[i-k];if(i+L<p+1) next[i]=L; //两种情况，画图可理解else{j=max(0,p-i+1); //p-i+1可能是负值，当p<i的时候while(i+j<m && x[i+j]==x[j])j++;next[i]=j;k=i; //i+next[i]一定>=k+next[k]，等于的时候更新k值正确性可画图模拟}}}void EKMP(char x[],int m,char y[],int n,int next[],int extend[]) //文本串是y，模式串是x{pre_EKMP(x,m,next);int j=0;while(j<n && j<m && x[j]==y[j]) j++;extend[0]=j;int k=0;for(int i=1;i<n;i++){int p=extend[k]+k-1;int L=next[i-k];if(i+L<p+1) extend[i]=L;else{j=max(0,p-i+1);while(i+j<n && j<m && y[i+j]==x[j])j++;extend[i]=j;k=i;}}}
关于这题的题意“这段密文的前半部份是加密过的，，后半部分是没有加密过的明文，现在这段密文被截获，但是明文的一部份损失了。”这个容易忽视，这位大牛报告很好
先把S全部都当作是密文的，然后把S全转换成明文，保存为T
这时，S中的密文部分就全部都变成了明文，而明文部分都变成了xxx（不用管是什么）。
然后可以发现，原来的S中的明文部分是S的后缀，而T中的明文部分是T的前缀。
所以，演变成了求S【i….n】中的与T的最长公共前缀，就是赤裸的拓展KMP问题了。
最后经过O(n)的枚举，不光要找到一个i满足extend[i]+i=len而且i>=extend[i]，才能保证密文至少占输入的串一半以上（因为输入的明文长度<密文长度）（也正是这个条件，保证了全部反转字符后可以用拓展KMP轻松解决）
//78MS 2072K #include<cstdio>#include<iostream>#include<cstring>using namespace std;char key[30],x[100100],y[100100];int Hash[200];int next[100100],extend[100100];void pre_EKMP(char x[],int m,int next[]){next[0]=m;int j=0;while(j+1<m&&x[j]==x[j+1]) j++;next[1]=j;int k=1;for(int i=2;i<m;i++){int p=k+next[k]-1;int L=next[i-k];if(L+i-1<p){next[i]=L;}else{j=max(0,p-i+1);while(i+j<m&&x[i+j]==x[j]) j++;next[i]=j;k=i;}}}void EKMP(char x[],int m,char y[],int n,int next[],int extend[]){pre_EKMP(x,m,next);int j=0;while(j<n&&j<m&&y[j]==x[j]) j++;extend[0]=j;int k=0;for(int i=1;i<n;i++){int p=k+extend[k]-1;int L=next[i-k];if(i+L-1<p){extend[i]=L;}else {j=max(0,p-i+1);while(j+i<n&&j<m&&y[j+i]==x[j]) j++;extend[i] = j;k=i;}}}int main(){int T;scanf("%d",&T);while(T–){scanf("%s%s",key,y);for(int i=0;key[i];i++){Hash[key[i] ] = i+'a' ;}int len=0;for(;y[len];len++){ //全部反转x[len]=Hash[y[len] ];}x[len]=0;EKMP(x,len,y,len,next,extend);int k;for(k=0;k<len;k++){if(k+extend[k]==len&&k>=extend[k])break;}for(int i=0;i<k;i++) printf("%c",y[i]);for(int i=0;i<k;i++) printf("%c",Hash[ y[i] ]);puts("");}return 0;}
不是每一次努力都有收获，但是，每一次收获都必须经过努力。
