[POJ 3974] Palindrome【Manacher】
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
Output
Sample Input
abcbabcbabcba abacacbaaaab END
Sample Output
Case 1: 13 Case 2: 6
Source
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 算法的核心如下:
- 初始化:set mxr = 0, id = 0
- 遍历新串:for each integer i ∈ [0, len), do step 3~5
- 继承已探索区间:if mxr > i, set pal[i] = min(mxr - i, pal[2 * id - i]), otherwise set pal[i] = 1
- 暴力扩展未探索区间:while str[i + pal[i]] == str[i - pal[i]], let i++
- 转换最右端点: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; }
发表评论