最长回文子串-马拉车

回文串是指是正着读和反着读都一样的字符串，比如abcba。

最长回文子串是指在一个字符串中能找到的最长回文串，如这个字符串最长回文字串是最后6个字符：abacacbaaaab

用马拉车算法求一个串中的最长回文子串：

1. 首先将字符串长度处理成奇数，如"abbc"处理成"$a#b#b#c#"。
2. 然后从左到右边遍历求出以每个字符为中心的回文半径Mp, 其中最大的那个回文半径就对应着最长的回文子串。

Manacher

算法实现如下：

图中id表示如果以这个下标为中心，回文半径最远可以到达的位置是mx（这表示区间(id,mx]与[mx",id)是对称的, id位置就是对称轴）。

马拉车的思想是利用左边已经求出的回文半径，帮助计算右边的回文半径。如果我们要求下标i的回文半径，那么：

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

计算回文半径Mp[i]:

1. 如果mx>i(图1,2)，即id处的回文半径能够覆盖当前位置，那么i关于id的对称位置i"一定也在以id为中心的回文串中。

   i"位于id左边，所以i"的结果前面已经算出来了，直接得出i"的回文半径就是Mp[i"] = Mp[2*id-i]。

   （图里左边的红色部分就是回文半径为Mp[i"]的回文串，右边是对称的部分）

   这时候计算i的回文半径还分两种情况:

   1. mx-i > Mp[2*id-i]
   2. mx-i < Mp[2*id-i]

   分别对应图1、2。Mp[i]的值选取两者中较小的那一个。

   因为图中只有同时被红色和绿色覆盖的，才关于i对称，其他的未知。

2. 如果，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 裸题