给两个串第一个串是翻译表（密文可以通过翻译表翻译成明文），第二个串是由密文+明文组成，前面是密文（完整的），后面是明文（未必完整），问能不能把第二个串补全，输出最短的一种可能。
一开始 用的string 和每次更新字符进行getnext
妥妥的 超时 kmp最好不要用string 速度太慢了
参考了 kuangbin的做法：
以s为原串做一次扩展KMP，得到extend数组，extend[i]表示原串以第i开始与模式串的前缀的最长匹配。经过O(n)的枚举，我们可以得到,若extend[i]+i=len且i>=extend[i]时，表示stringB即为该点之前的串，stringA即为该点之前的str串，最后输出即可。
就是原串和翻译后的串进行一次ekmp 然后进行判断输出即可
#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define LL long long
#define REP(i,N) for(int i=0;i<(N);i++)
#define CLR(A,v) memset(A,v,sizeof A)
//////////////////////////////////
#define inf 0x3f3f3f3f
#define N 100000+50
int nex[N];
int extend[N];
char p[N];
char s[N];
char table[N];
map<char,char>mp;
void EKMP(char s[],char t[])//s[]为主串，t[]为模式串
{
int i,j,p,l;
int len=strlen(t);
int len1=strlen(s);
memset(nex,,sizeof(nex));
memset(extend,,sizeof(extend));
nex[]=len;
j=;
while(j+<len&&t[j]==t[+j])j++;
nex[]=j;
int a=;
for(int i=;i<len;i++)
{
p=nex[a]+a-;
l=nex[i-a];
if(i+l<p+)nex[i]=l;
else
{
j=max(,p-i+);
while(i+j<len&&t[i+j]==t[+j])j++;
nex[i]=j;
a=i;
}
}
j=;
while(j<len1&&j<len&&s[j]==t[j])j++;
extend[]=j;
a=;
for(i=;i<len1;i++)
{
p=extend[a]+a-;
l=nex[i-a];
if(l+i<p+)nex[i]=l;
else
{
j=max(,p-i+);
while(i+j<len1&&j<len&&s[i+j]==t[j])j++;
extend[i]=j;
a=i;
}
}
} int main()
{
int cas;
RI(cas);
while(cas--)
{
RS(table);
RS(s);
rep(i,,)
mp[table[i]]='a'+i;
int len=strlen(s);
rep(i,,len-)
p[i]=mp[ s[i] ];
EKMP(s,p);
int k;
for(k=(len+)/;k<len;k++)
{
if(extend[k]+k>=len)//+k 意为当前坐标之前有几个字母 直接为k即可
break;
}
rep(i,,k-)
printf("%c",s[i]);
rep(i,,k-)
printf("%c",mp[s[i]]);
cout<<endl;
}
return ;
}