最长回文子串

给定一个字符串 SS，求出其最长回文子串的长度。

改造字符串

回文分为两种情况：奇回文（例如：“aabaa”\text{“aabaa”}）和偶回文（例如：“aabbaa”\text{“aabbaa”}）。“aabaa”\text{“aabaa”}的回文中心是 “b”\text{“b”}，而“aabbaa”\text{“aabbaa”}的回文中心是 $\text{“bb”} $。
为了避免两种回文情况的讨论，我们将每两个字符之间插入一个不曾出现的字符，统一改造为奇回文来处理，比如，将 $\text{“accahqiq”}$改造为$\text{“\$#a#c#c#a#h#q#i#q#”}$。开头$\text{“\$"}$为防止数组越界。对于改造后的字符串 SS，定义数组 p[i]p[i] 表示以 ii 为中心的最长回文半径。例如：

i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
s[i] $ # a # c # c # a # h # q # i # q #
p[i] 1 2 1 2 5 2 1 2 1 2 1 2 1 4 1 2 1

可以看出，p[i]−1p[i]-1 的最大值就是原字符串中最长回文子串的回文长度。
一下介绍的所有操作都是基于改造后的字符串 SS。

暴力解法(Brute force algorithm)

遍历每一个字符，以该字符为中心向两边查找，遇到两边不相等的字符则继续枚举下一个回文中心。其时间复杂度为 O(n2)O(n^2)，不可接受。

二分+字符串哈希(Binary algorithm and string hashing)

枚举回文中心，对于每一个回文中心二分答案（即 二分该中心的最大回文半径），找到回文半径的最大值。时间复杂度为 O(nlog⁡n)O(n\log n)，对于一些时限较为宽松、数据规模较小的问题是可行的 （如 POJ 3974\text{POJ 3974}），如果数据规模较大，妥妥地 TLE\text{TLE}（如 洛谷P3805\text{洛谷P3805}）。

马拉车算法(Manacher’s algorithm)

1975 年由 Manacher\text{Manacher} 发明。Manacher\text{Manacher} 算法（音译：马拉车算法），可以在 O(n)O(n) 的时间处理出以字符串中每一个字符为中心的回文串半径，由于将原字符串处理成两倍长度的新串，在每两个字符之间加入一个特定的特殊字符，因此原本长度为偶数的回文串就成了以中间特殊字符为中心的奇数长度的回文串了。下面将详细介绍马拉车算法的思想。

Manacher\text{Manacher} 算法思想

计算数组 p[i]\text{p[i]}

Manacher\text{Manacher} 算法的重点是是求解数组 p[i]p[i]。
设置两个变量，mxmx 和 idid 。定义mx=id+p[id]mx=id + p[id] ，也就是以 idid 为中心的最长回文的右边界。假设现在求p[i]p[i]，也就是以 ii 为中心的最长回文半径。

i<mxi<mx

如果 i<mxi < mx，那么p[i]=min⁡(p[2∗id−i],mx−i)p[i] = \min (p[2 * id - i], mx - i)。

现在证明当 i<mxi<mx，p[i]=min⁡(p[2∗id−i],mx−i)p[i] = \min (p[2 * id - i], mx - i)。
①jj 的回文串有一部分在 idid 的之外

上图中，黑色线段为 idid 的回文，ii 与 jj 关于 idid 对称，红线为 jj 的回文。那么根据代码此时 p[i]=mx−ip[i] = mx - i，即紫线。p[i]p[i]显然不可能更大也不可能更小。

假设右侧新增的紫色部分是p[i]p[i]可以增加的部分，那么根据回文的性质，aa 等于 dd ，也就是说 idid 的回文不仅仅是黑线，而是黑线+两条紫线，矛盾，所以假设不成立，故 p[i]=mx−ip[i] = mx - i，不可以再增加。
同理，我们先假设p[i]p[i]能减小，即p[i]<mx−ip[i]<mx-i，根据回文串的对称性，其对称点 jj 的回文长度一定也小于 mx−imx-i，矛盾，所以假设不成立，故 p[i]=mx−ip[i]=mx-i。
② jj 回文串全部在 idid 的内部

根据回文串的对称性 p[i]=p[j]p[i]=p[j]。
③jj 回文串左端正好与 idid 的回文串左端重合
根据代码，此时 p[i]=p[j]=mx−ip[i] = p[j]= mx - i，并且p[i]p[i]还可以继续增加，可以用循环直接暴力更新p[i]p[i]。

i>mxi>mx

当i>mxi>mx，暂时将 p[i]p[i] 置为 11，用循环暴力更新 p[i]p[i]。
（以上内容部分参考博文Manacher 算法。作者：刘毅 ）

模板 POJ 3974 Palindrome ↬\looparrowright

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 10000001000000 characters find and print the length of the largest palindrome inside this string.

Input

Your program will be tested on at most 3030 test cases, each test case is given as a string of at most 10000001000000 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

Translation

求到字符串的最长回文子串长度。

Code

二分+字符串哈希

时限15000ms15000ms，相当宽松。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define N 1000002
#define ull unsigned long long
using namespace std;
const ull base=131;
char s[N<<1];
ull _hash[N<<1],rehash[N<<1],p[N<<1];
void get_pow()
{
	int i;
	p[0]=1;
	for(i=1;i<N;i++) p[i]=p[i-1]*base;
}
int main()
{
	int times=0;
	get_pow();
	while(~scanf("%s",s+1))
	{
		if(!strcmp(s+1,"END")) break;
		int len=strlen(s+1);
		int i;
		/*------改造字符串------*/
		for(i=len<<1;i>0;i-=2)
		{
			s[i]=s[i>>1];
			s[i-1]='z'+1;
		}
		len=len<<1|1;
		s[len]='z'+1;
		/*-预处理顺序和逆序的哈希值-*/
		for(i=1;i<=len;i++) _hash[i]=_hash[i-1]*base+s[i]-'a'+1;
		for(i=len;i>=1;i--) rehash[i]=rehash[i+1]*base+s[i]-'a'+1;
		int ans=0;
		/*------枚举回文中心-----*/
		for(i=1;i<=len;i++)
		{
			int l=1;
			int r=min(i,len-i+1);
			int res=1;
			/*----二分回文半径----*/
			while(l<=r)
			{
				int mid=l+r>>1;
				ull l_hash=_hash[i]-_hash[i-mid]*p[mid];
				ull r_hash=rehash[i]-rehash[i+mid]*p[mid];
				if(l_hash==r_hash) //check顺序和逆序的哈希是否相同
				{
					res=mid;
					l=mid+1;
				}
				else r=mid-1;
			}
			ans=max(ans,res-1);//更新答案
		}
		printf("Case %d: %d\n",++times,ans); 
	}
	return 0;
}

Manacher\text{Manacher}算法

非常高效。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 1000003
using namespace std;
char s[N<<1];
int p[N<<1];
int len;
void remodel()
{
	int i;
	len=strlen(s+1);
	s[0]='$';
	for(i=len<<1;i>0;i-=2)
	{
		s[i]=s[i>>1];
		s[i-1]='{';
	}
	len=len<<1|1;
	s[len]='{';
	s[len+1]='\0';
}
int manacher()
{
	remodel();//改造字符串
	int id=1,mx=1,ans=-1;
	int i;
	for(i=1;i<=len;i++)
	{
		if(i<mx) p[i]=min(mx-i,p[id*2-i]);
		else p[i]=1;
		while(s[i-p[i]]==s[i+p[i]]) p[i]++;//暴力更新
		if(mx<i+p[i])//更改最长回文中心
		{
			id=i;//更新对称中心
			mx=i+p[i];//更新右边界
		}
		ans=max(ans,p[i]-1);//更新答案
	}
	return ans;
}
int main()
{
	int Case=0;
	while(~scanf("%s",s+1))
	{
		if(!strcmp(s+1,"END")) break;
		printf("Case %d: %d\n",++Case,manacher());
	}
	return 0;
}