HDU-4300-Clairewd’s message（KMP+特判）

博主链接

题目

题意：

先给你一个密码表。然后给你一个不一定完整的串。原串满足前一半是密码，后一半是明码。要求你最小的补全这个串。

题解：

设给的串长度为len,则1…(len+1)/2的字母一定是密码。我们将1…(len+1)/2的字母全部安装密码表转换成原文，然后将得到的串求Next数组。再根据Next数组求出最大的相等的前后缀（长度一定小于或等于len/2，题目要求），然后输出就可以。然后这里一定要先加一个特判是不是不存在相等的前后缀，也就是s[1]!=s[len],这时输出原串一次，再输出一次原串全解密的串.

代码：

#include<stdio.h>
#include<bits/stdc++.h>
#define met(a) memset(a,0,sizeof(a))
#define fup(i,a,n,b) for(int i=a;i<n;i+=b)
#define fow(j,a,n,b) for(int j=a;j>0;j-=b)
#define MOD(x) (x)%mod
using namespace std;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
typedef long long ll;
char s[maxn],s1[maxn];
char t[maxn];
char m[33];
int nex[maxn];
void Get_nex() {
	int j = 0;
	for (int i = 1; s[i]; i++) {
		while (s[i] != s[j + 1] && j != 0)j = nex[j];
		if (s[i] == s[j + 1] && i != 1)j++;
		nex[i] = j;
	}
}
int main() {
	int t,n;
	scanf("%d", &t);
	while (t--) {
		scanf("%s", m+1);
		scanf("%s", s+1);
		int len = strlen(s+1);
		for (int i = 1;i<=len+1; i++)s1[i] = s[i];
		for (int j = 1; j <= (len +1)/ 2; j++) {   //进行原串前半部分解密
			for (int i = 1; i <= 26; i++) {
				if (s[j] == m[i]) {
					s[j] = 'a' + i-1;
					break;
				}
			}
		}
		Get_nex();
		int nn =0;
		int a = nex[len];
		if (a == 0) {	//	如果不存在相等的前后缀
			printf("%s", s1 + 1);
			for (int j = (len+1)/2+1; j <= len; j++) {
				for (int i = 1; i <= 26; i++) {
					if (s[j] == m[i]) {
						s[j] = 'a' + i - 1;
						break;
					}
				}
			}
			printf("%s\n", s+1);
			continue;
		}
		while (a != 0) {	//找出最大的相等的前后缀且长度小于或等于len/2
			if (s[a] == s[len]) {
				if (a <= len / 2)nn = max(nn, a);
				a = nex[a];
			}
		}
		printf("%s", s1+1);
		for (int i = nn+1; i <= len -nn; ++i)printf("%c",s[i]);
		printf("\n");
	}
}