在处理字符串问题时,常常会遇到回文串。回文串是正着和反着都一样的字符串,比如"aba", "baab"等。

朴素做法

我们要如何找出最长的回文子串呢?

我们找回文串的时候,一般先确定回文串的中心,然后往两边尽可能的延伸。

回文串根据长度可以分为奇回文和偶回文,所以我们定义两个数组d1和d2,它们分别表示以i为中心,最长的奇回文和偶回文的半径。

string s;
int n = s.length();
int d1[maxn], d2[maxn];
for(int i=0; i<n; i++)
{
    d1[i] = 1;
    while(0<=i-d1[i] && i+d1[i]<n && s[i-d1[i]]==s[i+d1[i]])
        d1[i]++;
    
    d2[i] = 0;
    while(0<=i-d2[i]-1 && i+d2[i]<n && s[i-d2[i]-1]==s[i+d2[i]])
        d2[i]++;
}

朴素算法的时间复杂度很显然是O(n^2)的,这个算法效率太慢了,且还分为奇回文偶回文来计算,太麻烦了。

预处理字符串

我们可不可以将奇回文和偶回文一起处理,不分两个数组?

我们将原始的字符串进行一些处理,得到一个新的字符串,就可以很方便的计算了。

我们在每一个字符间,包括头和尾,都插入一个特殊的字符,比如#,当然这个字符得是原字符串一定不出现的字符才行。

原字符串: abba
预处理后: #a#b#b#a#

原字符串: aba
预处理后: #a#b#a#

经过这样的预处理后,我们得到的字符串长度为奇数,并且可以将d1和d2合并成一个数组。

计算最长回文子串

我们用p数组来记录以i为中心的最长回文串的半径。

i       0 1 2 3 4 5 6 7 8 9 10 11 12
s[i]    # c # a # b # b # a #  f  #
p[i]    1 2 1 2 1 2 5 2 1 2 1  2  1

观察到以i为中心的最长回文串的长度为p[i]-1

所以最长的回文子串的长度为max(p[i]-1)

计算最长回文子串的开始索引

知道了最长回文串的开始索引,我们就能找出最长的回文串是哪一个了。

还是以"cabbaf"为例

i       0 1 2 3 4 5 6 7 8 9 10 11 12
s[i]    # c # a # b # b # a #  f  #
p[i]    1 2 1 2 1 2 5 2 1 2 1  2  1

观察到p[6]=5是最长的半径,用6(i)-5(p[i])得到1,发现1正好是原始字符串"cabbaf"中a的索引号

再看一个奇回文的例子,p[1]=2,计算以c为中心的最长回文子串的开始索引,用1(i)-2(p[i])=-1,出现了负数,这可不行。

我们再在字符串前面加一个特殊符号’$‘,在末尾加’@',这两个字符也要保证原始字符串中绝对不出现。

i       0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
arr[i]  $ # c # a # b # b # a  #  f  #  @
p[i]    1 1 2 1 2 1 2 5 2 1 2  1  2  1  1

然后我们观察到最长回文串的开始索引等于int index = (i-p[i])/2

计算p数组

解决了以上的问题,我们该解决如何高效的计算p数组了。

我们设置两个变量,id和mx,id是当前所找到的边界最靠右的回文串的中心,mx是最右的回文串边界。即mx=p[id]+id

我们尽可能的利用回文串的性质来降低时间复杂度度。

假设当前遍历到i,要求p[i],2*mx-id是mx关于id对称的点,2*id-i是i关于id对称的点。

当前找到边界最靠右的回文串是s[2*id-mx…mx]

1

我们将会面临三种情况:

第一种:

2

蓝色线的区间是以2*id-i为中心最长的回文串的范围,根据回文串的对称性,我们知道此时p[i]=p[2*id-i]

第二种:

3

i+p[2*id-i] > mx,我们并不能确定mx之后的情况是怎么样的,所以只能先让p[i]=mx-i,然后根据朴素算法再慢慢向左右尽可能的拓展。

第三种:

i > mx的时候,我们让p[i]=1,然后根据朴素算法尽可能的向两边拓展。

模板:

char s[maxn];
char t[2*maxn];
int p[2*maxn];
int manacher()
{
	int len = strlen(s);
	// 预处理字符串
	int l=0;
	t[l++] = '$';
	t[l++] = '#';
	for(int i=0;i<len;i++)
	{
		t[l++] = s[i];
		t[l++] = '#';
	}
	t[l] = '@';
	int id = 0, mx = 0;
	int maxlen = 1;
	for(int i=0;i<l;i++)
	{
	        // 预设p[i]的值
		p[i] = mx>i ? min(p[2*id-i], mx-i) : 1;
		// 朴素算法向左右拓展,因为处理后的字符串头和尾都是特殊字符,所以不会越界
		while(t[i+p[i]] == t[i-p[i]])p[i]++;
		// 能否更新mx
		if(mx < p[i]+i)
		{
			mx = p[i]+i;
			id = i;
		}
		// 更新最长回文子串的长度
		if(maxlen < p[i]-1)
			maxlen = p[i]-1;
	}
	return maxlen;
}

Manecher算法的时间复杂度是O(n)

例题

洛谷P3805

4

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IO ios::sync_with_stdio(0)
#define DEBUG(x) cout<<"--->"<<(x)<<endl;
typedef pair<int, int> P;
const int maxn = 4e5+5;
const ll mod = 1e9+7;
const double eps = 1e-9;
using namespace std;


const int N = 11000000+5;
char s[N];
char t[2*N];
int p[2*N];
int manacher()
{
	int len = strlen(s);
	int l=0;
	t[l++] = '$';
	t[l++] = '#';
	for(int i=0;i<len;i++)
	{
		t[l++] = s[i];
		t[l++] = '#';
	}
	t[l] = '@';
	int id = 0, mx = 0;
	int maxlen = 1;
	for(int i=0;i<l;i++)
	{
		p[i] = mx>i ? min(p[2*id-i], mx-i) : 1;
		while(t[i+p[i]] == t[i-p[i]])p[i]++;
		if(mx < p[i]+i)
		{
			mx = p[i]+i;
			id = i;
		}
		if(maxlen < p[i]-1)
			maxlen = p[i]-1;
	}
	return maxlen;
}
int main()
{
	scanf("%s", &s);
	int ans = manacher();
	printf("%d\n", ans);
	return 0;
}