[POJ 3974] Palindrome【Manacher】

  • 2018-01-06
  • 0
  • 0

Problem:

Time Limit: 15000MS Memory Limit: 65536K

Description

Andy the smart computer science student was attending an algorithms class when the professor asked the students a simple question, "Can you propose an efficient algorithm to find the length of the largest palindrome in a string?"

A string is said to be a palindrome if it reads the same both forwards and backwards, for example "madam" is a palindrome while "acm" is not.

The students recognized that this is a classical problem but couldn't come up with a solution better than iterating over all substrings and checking whether they are palindrome or not, obviously this algorithm is not efficient at all, after a while Andy raised his hand and said "Okay, I've a better algorithm" and before he starts to explain his idea he stopped for a moment and then said "Well, I've an even better algorithm!".

If you think you know Andy's final solution then prove it! Given a string of at most 1000000 characters find and print the length of the largest palindrome inside this string.

Input

Your program will be tested on at most 30 test cases, each test case is given as a string of at most 1000000 lowercase characters on a line by itself. The input is terminated by a line that starts with the string "END" (quotes for clarity).

Output

For each test case in the input print the test case number and the length of the largest palindrome.

Sample Input

abcbabcbabcba
abacacbaaaab
END

Sample Output

Case 1: 13
Case 2: 6

Source

Seventh ACM Egyptian National Programming Contest

Solution:

这是最长回文子串 Manacher 算法的模板题。

【Manacher 算法】(详见 【转载】知乎:有什么浅显易懂的Manacher Algorithm讲解?

首先将一个特殊字符(可以是 '#')间隔插入原串的每两个字符之间,再在开头添加另一个特殊字符(可以是 '$'),以统一奇偶串,例如:

  • abaca => $#a#b#a#c#a#
  • abacbb => $#a#b#a#c#b#b#

这样所有的回文串长度就都是奇数了。

令 str 表示新串,len 表示新串长度,pal[i] 表示新串以 str[i] 为中心的最长回文子串向两边扩展的长度,例如:

  • 回文子串 "#a#b#a#" 的 pal 值为 4,回文子串 "#b#b#" 的 pal 值为 3,etc.

再令 mxr 表示当前右端点最右的回文子串的右端点(绕晕中~~),id 表示该回文子串的中心,则 Manacher 算法的核心如下:

  1. 初始化:set mxr = 0, id = 0
  2. 遍历新串:for each integer i ∈ [0, len), do step 3~5
  3. 继承已探索区间:if mxr > i,  set pal[i] = min(mxr - i, pal[2 * id - i]), otherwise set pal[i] = 1
  4. 暴力扩展未探索区间:while str[i + pal[i]] == str[i - pal[i]], let i++
  5. 转换最右端点:if i + pal[i] mxr, set mxr = i + pal[i], id = i

第 3 步的正确性证明如下:

  • 当 mxr > i 时,i 仍在最右子串内,2 * id - i 是 i 的对称点。
  • 当以 2 * id - i 为中心的回文串不超出最右回文串时,以 i 为中心的回文串与之对称,长度至少为 pal[2 * id - i]
  • 反之当超出最右回文串时,以 i 为中心的回文串与其在最右回文串中的部分对称,长度至少为 mxr - i

代码的最终实现很精简。

【附加内容】
据说通过 Manacher 可以得到一个推论:一个串本质不同的回文子串个数最多为 len 个,每次 pal[i] 增加的时候,就说明出现了新的本质不同的回文子串。

Code: O(Tn) [9924K, 235MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

char str[2000005];
int pal[2000005];
int cas = 0, len;

inline int Manacher(char *str, int len){
	for(register int i = len; i >= 0; i--){
		str[i + 1 << 1] = str[i];
		str[(i << 1) + 1] = '#';
	}
	str[0] = '$';
	len = len + 1 << 1;
	// Pre-procession of inserting special characters
	int mxr = 0, id = 0;
	for(register int i = 0; i < len; i++){
		pal[i] = (mxr > i) ? min(mxr - i, pal[2 * id - i]) : 1;
		while(str[i + pal[i]] == str[i - pal[i]]) pal[i]++;
		if(i + pal[i] > mxr) mxr = i + pal[i], id = i;
	}
	// Core of Manacher Algorithm
	int maxl = 0;
	for(register int i = 0; i < len; i++) maxl = max(maxl, pal[i]);
	return maxl - 1;
}

int main(){
	while(scanf("%s", str) != EOF && str[0] != 'E'){
		len = strlen(str);
		printf("Case %d: %d\n", ++cas, Manacher(str, len));
	}
	return 0;
}

评论

还没有任何评论,你来说两句吧



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai