HDU 4300

题目就是给一串密文 + 不完整的明文，求翻译出最终的明文（要最短），以 密文 + 明文的形式输出。

我的做法大致是直接把给出的串 $b$ 直接翻译成 $a$，考虑 $b$ 的一个最长的后缀 $[i, n]$ 与 $a$ 前缀 $[1, i]$ 能匹配，用 EXKMP。

但是过不去（捂脸）

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <cctype>
#include <vector>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int mo=1e9+7;
inline int read(){
	char ch=getchar();int x=0, f=1;
	while(!isdigit(ch)){if(ch=='-') f=-1; ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x*f;
}
inline void write(int x){
    if(x<0) putchar('-'), x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
inline int ksm(int a, int b){
	int ret=1;
	for(; b; b>>=1, a=1ll*a*a%mo)
		if(b&1) ret=1ll*ret*a%mo;
	return ret;
}
const int N=1e5+5;
namespace Solution{
	int n, Z[N], EK[N];
	char a[N], b[N], Mp[27], Mp2[27];
	signed work(){
		memset(Z, 0, sizeof(Z));
		memset(EK, 0, sizeof(EK));
		memset(Mp, 0, sizeof(Mp));
		memset(Mp2, 0, sizeof(Mp2));
		scanf("%s", Mp);scanf("%s", b+1);n=strlen(b+1);
		for(int i=0; i<26; i++) Mp2[Mp[i]-'a']='a'+i;
		for(int i=1; i<=n; i++) a[i]=Mp2[b[i]-'a'];
		Z[1]=n;
		for(int i=2, l=0, r=0; i<=n; i++){
			if(i<=r) Z[i]=min(Z[i-l+1], r-l+1);
			while(i+Z[i]<=n&&a[i+Z[i]]==a[1+Z[i]]) Z[i]++;
			if(i+Z[i]-1>r) l=i, r=i+Z[i]-1;
		}
		for(int i=1, l=0, r=0; i<=n; i++){
			if(i<=r) EK[i]=min(Z[i-l+1], r-l+1);
			while(i+EK[i]<=n&&b[i+EK[i]]==a[1+EK[i]]) EK[i]++;
			if(i+EK[i]-1>r) l=i, r=i+EK[i]-1;
		}
		int fin=n;
		for(int i=(n+1)/2; i<=n; i++)
			if(EK[i]+i>=n){
				fin=i;break;
			}
		for(int i=1; i<fin; i++) printf("%c", b[i]);
		for(int i=1; i<fin; i++) printf("%c", a[i]);
		puts("");
		return 0;
	}
	//将串 b 翻译为明文 a，则若串 b 的一个后缀 [i, n] 跟 a 的匹配长度 >=i 则成功为 i-1 
}
signed main(){
	int T=read();while(T--) Solution :: work();
	return 0;
}