next[i]是模式串跟自己的最长公共前缀
x[i ... m-1] 与 x[0 ... m-1] 的最长公共前缀是next[i]
extend[i]是主串跟模式串的最长公共前缀
y[i ... n-1] 与 x[0 ... m-1] 的最长公共前缀是extend[i]
namespace e_kmp{
int next[100], extend[100];//大小为 模式串长度 主串长度
void pre_ekmp(const char x[], int m){
next[0] = m;
int j = 0;
while(j + 1 < m && x[j] == x[j+1]) j++;
next[1]=j;
int k = 1;//从k点算，前缀长度+k 能达到最远位置
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);
while(i+j < m && x[i+j] == x[j]) j++;
next[i] = j;
k = i;
}
}
}
void ekmp(const char x[], int m, const char y[], int n){//模式串 len 主串 len
pre_ekmp(x,m);
int j = 0;
while(j < n && j < m && x[j] == y[j]) j++;
extend[0] = j;
int k = 0;//从k点算，前缀长度+k 能达到最远位置
for(int i = 1; i < n; i++){
int p = extend[k] + k -1;//思路跟求next一样，只不过前者是模式串跟自己比较，后者是主串跟模式串比较
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;
}
}
}
}
例题
POJ4300
题目大意，第一行输入一个t，代表有t组样例。对于每组样例，第一行给出一个加密表tab，tab[i]表示第i个小写字母加密后的字母，如下面样例中加密表就是a -> a,b -> b,c -> c（就是不变）。
第二行表示截获的数据。一个正常的数据组成是XXXXabcd,x表示加密的字母，abcd表示原文。比如将abc处理成数据就是XXXabc,前半部分是原文根据加密表生产，后半部分是原文。这是一个正常的数据组成。
但是，截获到的数据不完整，后半部分原文丢失了几个字母，让你恢复出原文是什么（尽可能短）。
//input
1
abcdefghijklmnopqrstuvwxyz
abcdab
//output
abcdabcd
思路，截获到的数据是S = [............XXXX............][......abc......],
前半部分是加密部分，后面部分是缺失字母的原文。不论是密码还是原文，都当成密码按照加密表解密后得到：
T = [............abcd............][......???......],密码部分变成了原文，原文部分变成了无用信息，不知道是啥。
可以根据S和T找到密码部分和原文部分的分界点，就是中括号的空隙那里。以S为主串T为模式串构造前缀数组extend[],设分界点为i(原文部分第一个字符)。
满足 extend[i] >= S.len - i且i >= extend[i]
找到i就可以恢复原来数据。
对于样例：
S = [abcdab]
T = [abcdab]
extend[i]={4,0,0,0,2,0} i = 0 1 2 3 4 5
原文部分一定在S右半部分，因为密码部分没有丢失
s[5]处后缀是ab,长度是2，extend[5]也是2(T中有长度为2的前缀)，并且i=5>extend[5]=2,说明i在右半部分。
从左到右找第一个满足条件的位置就是分界点。（尽可能使原文短）
所以S = [abcd ab]原数据为S = [abcd abcd]
ac代码
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
namespace e_kmp{
int next[1000010], extend[1000010];
void pre_ekmp(const char x[], int m){
next[0] = m;
int j = 0;
while(j + 1 < m && x[j] == x[j+1]) j++;
next[1]=j;
int k = 1;//从k点算，前缀长度+k 能达到最远位置
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);
while(i+j < m && x[i+j] == x[j]) j++;
next[i] = j;
k = i;
}
}
}
void ekmp(const char x[], int m, const char y[], int n){//模式串 len 主串 len
pre_ekmp(x,m);
int j = 0;
while(j < n && j < m && x[j] == y[j]) j++;
extend[0] = j;
int k = 0;//从k点算，前缀长度+k 能达到最远位置
for(int i = 1; i < n; i++){
int p = extend[k] + k -1;//思路跟求next一样，只不过前者是模式串跟自己比较，后者是主串跟模式串比较
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;
}
}
}
}
char tab[27],rtab[27],s[1000010],tt[1000010];
int len;
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%s",tab);
for(size_t i=0;i<tab[i];i++){
rtab[tab[i]-'a'] = i + 'a';
}
scanf("%s",s);
len = strlen(s);
for(size_t i=0;i<len;i++){
tt[i] = rtab[s[i]-'a'];
}
e_kmp::ekmp(tt,len,s,len);
int aci=len;
for(size_t i=0;i<len;i++){
if(e_kmp::extend[i] >= len-i && i >= e_kmp::extend[i]){
//cout<<i<<" "<<e_kmp::extend[i]<<endl;
aci=i;
break;
}
}
for(int i=0;i<aci;i++){
printf("%c",s[i]);
}
for(int i=0;i<aci;i++){
printf("%c",tt[i]);
}printf("\n");
}
return 0;
}
