最长回文子串-马拉车

最长回文子串-马拉车

3 years ago

source link: https://www.kirito41dd.cn/manacher/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

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

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

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

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

Manacher

算法实现如下：

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

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

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

计算回文半径Mp[i]:

如果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对称，其他的未知。
如果，mx <= i(图3)，那么i的回文半径只能通过一次次比较求得。

细节见代码，返回值是最长回文串长度。

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 裸题

Recommend