题目链接：https://cn.vjudge.net/contest/276379#problem/J
感觉讲的很好的一篇博客：https://subetter.com/articles/extended-kmp-algorithm.html
题目大意：这是一个编译密码的题目，首先给你26个字母分别重新编码后的对应的字母，然后再给你一个字符串，字符串的前一部分是编译过后的，后一部分是编译之前的，但是后一部分可能会有损失，问你用尽量少的字符，将整个字符串补起来，也就是前面是暗文，后面是明文。
具体思路：扩展kmp的裸题， 我们可以另外开一个字符，这个字符存储的是编译过后的，我们现在把初始密码串比喻成s1，编译过后的密码串比喻成s2，这个样的话，我们直接找出s2中的后缀中，满足是s1的前缀的最长的找出来，这个就是残缺的暗文，前面的就是明文了。
对于扩展kmp的理解：首先说一下我理解的扩展kmp的作用，我们假设当前有一个字符串t，长度是len。t[i]代表的是以字符串的第i位开始，以t[len-1]为截止位置的t的子串，然后nex[i]的作用就是求t[i]和t的最大前缀和的匹配数。
其实extend的作用和nex的具体实现内容是一样的，因为在求nex的时候，我们当前是以t为模板串，t[i]是子串。在求extend的时候，我们是以t为模板串，s是对比串的。
AC代码：
1 #include<iostream> 2 #include<stack> 3 #include<iomanip> 4 #include<stdio.h> 5 #include<cmath> 6 #include<algorithm> 7 #include<string> 8 #include<map> 9 #include<cstring> 10 #include<vector> 11 using namespace std; 12 # define ll long long 13 const int maxn = 1e6+10; 14 char str[maxn],com[maxn]; 15 char tmp[maxn]; 16 int nex[maxn],extend[maxn]; 17 map<char,char>vis; 18 void getnex(int len) 19 { 20 int a=0,p=0; 21 nex[0]=len;//第0位是自己 22 for(int i=1; i<len; i++) 23 { 24 if(i>=p||i+nex[i-a]>=p) 25 { 26 if(i>=p) 27 p=i; 28 while(p<len&&tmp[p]==tmp[p-i]) 29 p++; 30 nex[i]=p-i; 31 a=i; 32 } 33 else 34 nex[i]=nex[i-a]; 35 } 36 } 37 void exkmp(int len1,int len2) 38 { 39 getnex(len2); 40 int a=0,p=0; 41 for(int i=0; i<len1; i++) 42 { 43 if(i>=p||i+nex[i-a]>=p) 44 { 45 if(i>=p) 46 p=i; 47 while(p<len1&&p-i<len2&&str[p]==tmp[p-i]) 48 p++; 49 extend[i]=p-i; 50 a=i; 51 } 52 else 53 extend[i]=nex[i-a]; 54 } 55 } 56 int main() 57 { 58 int T; 59 scanf("%d",&T); 60 while(T--) 61 { 62 scanf("%s",com); 63 scanf("%s",str); 64 for(int i=0; i<26; i++) 65 { 66 vis[com[i]]='a'+i; 67 } 68 int len=strlen(str); 69 for(int i=0; i<len; i++) 70 { 71 tmp[i]=vis[str[i]]; 72 } 73 exkmp(len,len); 74 int i; 75 for( i=0;i<len;i++){ 76 if(i+extend[i]>=len&&i>=extend[i])break;//求满足情况的前缀 77 } 78 for(int j=0;j<i;j++){ 79 printf("%c",str[j]); 80 } 81 for(int j=0;j<i;j++){ 82 printf("%c",vis[str[j]]); 83 } 84 printf("\n"); 85 } 86 return 0; 87 }