求字符串的最长回文子串--最直观的“马拉车算法”分析

使用马拉车算法(曼切斯特算法)求解字符串的最长回文子串问题。用一个数组p[i]来记录以字符s[i]为中心的最长回文子串向左/右扩张的长度,当 p[j]>=right - i 时,以s[i]为中心的回文子串,其向右至少会扩张到right的位置,也就是说p[i]>=right - i,所以先设置p[i]=right-i。至于right位置之后的部分是否对称,就只能老老实实去匹配了。

首先用一个非常巧妙的方式,将所有可能的奇数/偶数长度的回文子串都转换成了奇数长度:在每个字符的两边都插入一个特殊的符号。比如 abba 变成 #a#b#b#a#, aba变成 #a#b#a#。 为了进一步减少编码的复杂度,可以在字符串的开始加入另一个特殊字符,这样就不用特殊处理越界问题,比如$#a#b#a#(注意,下面的代码是用C语言写就,由于C语言规范还要求字符串末尾有一个’\0’所以正好OK,但其他语言可能会导致越界)

下面以字符串12212321为例,经过上一步,变成了 S[] = “$#1#2#2#1#2#3#2#1#”;

然后用一个数组p[i] 来记录以字符S[i]为中心的最长回文子串向左/右扩张的长度(包括S[i],也就是把该回文串“对折”以后的长度),比如S和P的对应关系:

S # 1 # 2 # 2 # 1 # 2 # 3 # 2 # 1 #

P 0 1 0 1 4 1 0 3 0 1 0 5 0 1 0 1 0

p[i]的含义如下图所示:

马拉车算法中p[i]含义

那么怎么计算P[i]呢?

设变量center表示最大回文子串中心的位置,right是最大回文子串的边界,j是i关于center的对称点。

计算p[i]的方法如图所示:

马拉车算法中计算p[i]的方法

注意

在上图中,当 p[j]>=right - i 时,以s[i]为中心的回文子串其向右至少会扩张到right的位置,也就是说P[i]>=right - i,所以先设置p[i]=right-i;至于right位置之后的部分是否对称,就只能老老实实去匹配了!!!

下面是我做leetcode上的题目最长回文子串Palindromic-Substring的源代码:

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Solution {
public:

string preProcess(string s)
{

int n = s.length();
string ret = "$";

for (int i = 0; i < n; ++i)
ret += "#" + s.substr(i, 1);
ret += "#";

return ret;
}

string longestPalindrome(string s) {
if(s.length() == 0)
return "";

string str = preProcess(s);
int n = str.length();

vector<int> p(n, 0);
int center = 0, right = 0;
int maxLen = 0;
int start;
bool finish;

for (int i = 1; i < n-1; ++i)
{
finish = false;
if(i < right)
{
int j = 2*center-i;
if(p[j] < right-i)
{
finish = true;
p[i] = p[j];
}
else
{
p[i] = right-i;
}
}
else
{
p[i] = 0;
}

if(finish == false)
{
while(str[i+(1+p[i])] == str[i-(1+p[i])])
++ p[i];
}

if(p[i] + i > right)
{
center = i;
right = i + p[i];
}

if(p[i] > maxLen)
{
maxLen = p[i];
start = i;
}
}

return s.substr((start-1-maxLen)/2, maxLen);
}
};

参考博客:

http://www.felix021.com/blog/read.php?2040
http://blog.csdn.net/hustcqb/article/details/12253635