[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;
}
发表评论