目录

马拉车-Manacher

求最长回文子串

求一个串中的回文子串,首先将字符串处理成奇数个。

"abbc"处理成Ma = "$ a # b # b # c #"

然后求出以每个字符为中心的回文半径Mp

最大的那个回文半径就对应着最长的回文子串

代码中id指以这个点为中心半径可以达到右边最远,达到的位置是mx

2*id-i 指的是i关于 id的对称位置i",(i肯定在id的右边,因为是从左往右遍历处理)

设当前位置为i,要计算Mp[i]:

如果,mx>i(图1,2),即id处的回文半径能够覆盖当前位置,那么i的对称位置i"一定也在以id为中心的回文串中,并且 i"位于id左边,已经处理过,Mp[2*id-i]就是i"的回文半径。

这时候计算i的回文半径还分两种情况。mx-i > Mp[2*id-i]mx-i < Mp[2*id-i],分别对应图1,2。Mp[i]的值选取两者中小的那一个。因为图中只有同时被红色和绿色覆盖的,才关于i对称,其他的未知。

/算法/manacher.png

如果,mx <= i(图3),那么i的回文半径只能通过一次次比较求得。

细节见代码

 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
namespace Manacher{
	const int MAXN = 100;//字符串最大长度
	char Ma[MAXN*2];//处理后的字符串
	int Mp[MAXN*2];//每个位置的回文半径,max(Mp[i])-1就是最长回文长度
	int Manacher(const char s[], int len){
		int l = 0, ret = 0;
		Ma[l++] = '$';
		Ma[l++] = '#';
		for(int i = 0; i<len; i++){
			Ma[l++] = s[i];
			Ma[l++] = '#';
		}
		Ma[l] = 0;
		int mx = 0, id = 0; //从id处回文半径可以达到mx处
		for(int i = 0; i < l; i++){
			Mp[i] = mx > i ? min(Mp[2*id-i], mx - i) : 1;
			while(Ma[i + Mp[i]] == Ma[i - Mp[i]]) Mp[i]++;
			ret = max(Mp[i]-1,ret);
			if(i + Mp[i] > mx){
				mx = i + Mp[i];
				id = i;
			}
		}
		return ret;
	}
}

例题

POJ3974 裸题