Manacher算法-leetcode-5-最长回文子串

缘起

题目链接在此最长回文子串

本文介绍一下最长回文子串的Manacher算法（马拉车）. 最长回文子串在亚马逊的面试中问到过.

分析

题意很裸

1
2
3
4
5
6
7
8
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"

其实，最长回文子串的求法有很裸的暴力算法——逐个扫描各个元素，然后扩大半径. 注意，回文串有奇数长度的回文串与偶数长度的回文串两种. 但是复杂度显然是O(n^2)的，此题其实可以使用暴力，毕竟n至多只有1000. 但是一旦n到达了10w这个级别的话，就一定超时.

本文的Manacher算法其实就是上述暴力算法的优化. 优化基于一个不等式，就可以将O（n^2）的算法优化到O(N).

​ 图1

那么怎么优化呢? 见上面的图1. 假设id是当前最大回文子串的中心. max是最大回文子串的半径. 那么现在考虑求i>id的r[i]（其中r[i]定义为以str[i]为中心的回文子串的半径,例如aba, 则r[0]=1,r[1]=2,r[2]=1. 你可以把回文半径理解为对折回文子串之后的长度。 注意，回文子串的半径>=1, 最差就是自己嘛~ 例如”a”自己就构成一个回文子串,只不过长度为1而已）.

我们断言

1
如果i<id+max-1(即i在[id, id+max-1)范围内，因为id都知道了，那么id肯定是求过的), 则r[i]>=min{r[2*id-i], id+max-i}

这是显然的, 因为查看图1，L1和L2一定是全等的. 而i关于id的对称点是2*id-i.

所以我们可以知道Manacher算法比暴力算法优化的地方在于——考察一个新的点的半径的时候不需要从1开始逐步扩大半径考察了, 只需要从一个min{r[2*id-i], id+max-i}开始考察即可

那对于 i>=id+max-1的怎么办? 那就只能老老实实的从1开始逐步扩大咯

但是为了对付此题, 我们对字符串进行了预处理.

无论是奇回文串还是偶回文，我们只需通过一个非26个英文字母的#来填充，则都变成奇回文. 即

aba这种奇回文变成 #a#b#a#, 而abba这种偶回文被填充为#a#b#b#a# 也是奇回文. 这样就统一了. 还有，在扩大半径的时候，防止越界到负索引，可以在字符串的0索引设置为诸如 ‘$’ 这种字符， 则因为C语言字符串末尾是’\0’, 所以必然不相等， 就不会数组越界了. 这是属于编码优化的点

说实话，leetcode使得我写的代码真丑~

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
#include <stdio.h>
#define MIN(x,y) ((x)<(y)?(x):(y))

char * longestPalindrome(char * s)
{
	char t[3000];
	int rr[3000];
	t[0] = '$';
	int i = 0,j = 1;
	while(s[i])
	{
		t[j++] = '#';
		t[j++] = s[i++];
	}
	t[j++] = '#';
	t[j] = 0;  // 预处理结果放进t中
	int id = 1, _max = 1; // 最大回文半径以及实现最大回文半径的中心(初始值就是t[1]='#', 所以从t[2]开始考察)
	i = 2;
	rr[1] = 1;
	while(t[i])
	{
		int r = i<id+_max-1?MIN(rr[(id<<1)-i],id+_max-i):1;
		while(t[i-r]==t[i+r])r++;
		if ((rr[i]=r)>_max) id = i,_max = rr[i];
		i++;
	}
	// 最长回文子串就是 [id-_max+1,...,id+_max-1], 从而找到s和t之间的映射关系是关键. 即s上的索引i对应t上的哪个索引. 不难知道 t[2*i+2]=s[i]
	// 不论是奇回文还是偶回文, t[id-_max+1]和t[id+_max-1]都是#, 则t[id-_max+2]和t[id+_max-2]就是真正的字符,则根据t[2*i+2]=s[i]可知, 对应s上的范围就是(i-_max)>>1和(id+_max-4)>>1
	s[((id+_max)>>1)-1] = 0;
	return s+((id-_max)>>1);
}

ac情况

执行结果：

通过

显示详情

执行用时 :8 ms, 在所有 C 提交中击败了96.27%的用户

内存消耗 :7.1 MB, 在所有 C 提交中击败了83.33%的用户

可见，Manacher算法在本题的表现还是比较优秀的.