西宁 专业网站建设重庆网站设计

题目链接：点击打开链接

题目描述：给定一个字母转换表，然后给一个字符串，字符串的前一部分经字母转换表转换过之后的字符，字符串的后面一部分是未经转换之前的，后面的部分可能不完整，但前面被转换过之后的一定是完整的，求补充不完整的部分（当然也有可能是完整的，如果是完整的直接输出即可），要求尽可能的短？

解题思路：扩展KMP算法（匹配前缀）

分析：相当于让字符串的后面部分尽可能长的匹配前面的部分，所以我们将原串st复制给str1,然后根据转换表，把st全部逆转回来；然后将st当作模板串，str1为带匹配的串，从str1[(len+1)/2]开始匹配即可

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#define MAXN 100010
using namespace std;void getNext(char* x,int m,int* exnext){exnext[0]=m;int j=0;while(j+1<m&&x[j]==x[j+1]) j++;exnext[1]=j;int k=1;for(int i=2;i<m;++i){int p=exnext[k]+k-1;int L=exnext[i-k];if(i+L<p+1) exnext[i]=L;else{j=max(0,p-i+1);while(i+j<m&&x[i+j]==x[j]) j++;exnext[i]=j;k=i;}}
}
void EKMP(char* x,int m,char* y,int n,int* exnext,int* extend){getNext(x,m,exnext);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=exnext[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 ascii[30];
char st1[MAXN];
char st[MAXN];
int exnext[MAXN];
int extend[MAXN];
int main(){int T;scanf("%d",&T);while(T--){scanf("%s",st1);scanf("%s",st);for(int i=0;i<26;i++)ascii[st1[i]-'a']='a'+i;int len=strlen(st);memcpy(st1,st,len);for(int i=0;i<len;++i)st[i]=ascii[st[i]-'a'];EKMP(st,len,st1,len,exnext,extend);int i;for(i=(len+1)/2;i<len;i++) if(extend[i]==len-i)break;for(int j=0;j<i;++j) printf("%c",st1[j]);for(int j=0;j<i;++j) printf("%c",st[j]);printf("\n");}return 0;
}