Light OJ 1258 Making Huge Palindromes KMP构造回文串
KMP   发布于 2019-07-21   400人围观  0条评论
KMP   发表于 2019-07-21   400人围观  0条评论

Description

A string is said to be a palindrome if it remains same when read backwards. So, 'abba', 'madam' both are palindromes, but 'adam' is not.

Now you are given a non-empty string S, containing only lowercase English letters. The given string may or may not be palindrome. Your task is to make it a palindrome. But you are only allowed to add characters at the right side of the string. And of course you can add any character you want, but the resulting string has to be a palindrome, and the length of the palindrome should be as small as possible.

For example, the string is 'bababa'. You can make many palindromes including

bababababab

babababab

bababab

Since we want a palindrome with minimum length, the solution is 'bababab' cause its length is minimum.

Input

Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case starts with a line containing a string S. You can assume that 1 ≤ length(S) ≤ 106.

Output

For each case, print the case number and the length of the shortest palindrome you can make with S.

Sample Input

4
bababababa
pqrs
madamimadam
anncbaaababaaa

Sample Output

Case 1: 11
Case 2: 7
Case 3: 11
Case 4: 19

题目大意:

给你一个串,让你从串的右侧尾部添加一些字符(可以是0个)使得这个串成为一个回文串,并输出构成的最短的回文串的长度。

题解:

这题听说有Manacher做法,但是那个做法我并没有完全理解,所以这里使用更好理解的KMP算法来实现。

首先我们要清楚一点,我们将原串翻转然后接到原串的尾部,一定能够构成一个回文串。

但是这个回文串不一定是长度最短的。

那么最短的是什么样的呢?我们仔细观察一下,只有拼接的中间出现重复时,回文串才有可能更短。

而中间的段的最长重复的部分本质上是翻转串的前缀和原串的后缀的重合部分。

这段重合部分我们只需要魔改一下KMP的匹配过程就好了。

然后答案就是2*原串长度-中间部分匹配的重复串的长度。

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int T;
int len;
const int maxn = 1e6+5;
char s[maxn],sp[maxn];
int nxt[maxn];
void KMP_pre(){
	int j = 0;
	nxt[1] = 0;
	for(int i = 2;i <= len;++i){
		while(j && sp[j+1] != sp[i])j = nxt[j];
		if(sp[j+1] == sp[i])j++;
		nxt[i] = j;
	}
	return;
}
int ans = 0;
void KMP(){
	int j = 0;
	for(int i = 1;i <= len;++i){
		while(j && sp[j+1] != s[i])j = nxt[j];
		if(sp[j+1] == s[i])j++;
	}
	ans = j;
	return;
}
int main(){
	scanf("%d",&T);
	getchar();
	for(int cas = 1;cas <= T;++cas){
		scanf("%s",s+1);
		len = strlen(s+1);
		for(int i = 1;i <= len;++i)sp[i] = s[i];
		reverse(sp+1,sp+len+1);
		KMP_pre();
		ans = 0;
		KMP();
		printf("Case %d: %d\n",cas,len*2 - ans);
	}
	return 0;
}

 

上一篇: Light OJ 1268 Unlucky Strings KMP DP矩阵快速幂优化

下一篇: HDU 3336 Count the string KMP(瞎搞)

立即登录,发表评论
没有帐号?立即注册
0 条评论