什么是Manacher算法(马拉车算法)
Manachar算法主要是处理字符串中关于回文串的问题的，它本质上是对枚举中心法确定回文串的优化，使得算法可以在 O（n） 的时间处理出以字符串中每一个字符为中心的回文串半径。
由于回文字符串以其长度来分，可以分为奇回文（其长度为奇数）、偶回文（其长度为偶数），一般情况下需要分两种情况来寻找回文，马拉车算法为了简化这一步，对原始字符串进行了处理，在每一个字符的左右两边都加上特殊字符（肯定不存在于原字符串中的字符），让字符串变成一个奇回文简化算法
暴力解法
对于寻找最长回文串，我们能想到的就是枚举每一个子串，看这些子串是否为回文串，但这个时候算法的时间复杂度为\(O(N^3)\)，是无法接受的。 1
2
3
4
5
6
7
8
9
10
11int n=s.size()
for(int i=0;i<n;++i)
for(int j=i+1;j<n;++j){
int l= i,r=j;
while(l<r&&s[l]==s[j]){
++l;
--r;
}
int len=j-i+1;
if(l>=r) maxLen=len>maxLen?len:maxLen;
}
中心枚举法
枚举以每个元素为中心时，找到中心位置（可能是一个位置，也可能是两个位置）往左右两端进行扩展； 时间复杂度\(O(n^2)\);我们知道回文串一定是对称的，所以我们可以每次循环选择一个中心，进行左右扩展，判断左右字符是否相等即可。 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22inline int expaned(string& s,int r,intl){
while(l>=0&&r<s.size()&&s[i]==s[j]){
++r;
--l;
}
return r-l+i;
}
string longestPalindrome(sring& s){
int n=s.size();
if(n<=1) return s;
int start=0,end=0;
for(int i=0;i<n;++i){
int len_1=expand(s,i,i);
int len_2=expand(s,i,i+1);
int len=max(len_1,len_2);
if(len>end-start){
start=i-((len-1)>>1);
end=i+(len>>1);
}
}
return s.substr(start,end-start+1);
}
动态规划
回文串问题同样能使用动态规划问题解决，其主要思想也是从中心枚举法得出，但是能够省略较多的重复比较，但是为了维护二维dp数组也要加入其O(n)的复杂度，因此总的时间复杂度为\(O(N^2)\) 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
37string longestPalindrome(string s) {
//dp[i][j]:表示s[i]是否等于s[j],相等且回文则置为true，否则为false
//初始条件：dp[i][i]=true;
//状态转移方程：
//①若i和j是相邻的即i+1=j且s[i]==s[j],则dp[i][j]=true
//②若不相邻，则判断内侧是否为true，若dp[i+1][j-1]=true&&s[i]==s[j],则dp[i][j]=true
//通过增加两变量记录当前回文串的最长长度Maxlen,初始为1,以及记录回文串的下标开始index_min，初始为最后一个元素
//算法的时间复杂度为O(n*n)
int len=s.size();
if(len==0||len==1)
return s;
vector<vector<bool>> dp(len,vector<bool>(len,false));
for(int i=0;i<len;i++)
dp[i][i]=true;
int Maxlen=1,index_min=len-1;
for(int i=len-2;i>=0;i--)
{
for(int j=i+1;j<len;j++)
{
if(s[i]==s[j])//如果两元素相等
{
if(j==i+1)//如果相邻
dp[i][j]=true;
else //不相邻，判断两元素内部是否为回文串
if(dp[i+1][j-1])
dp[i][j]=true;
if(dp[i][j]&&Maxlen<j-i+1)//更新Maxlen和index_min
{
Maxlen=j-i+1;
index_min=i;
}
}
}
}
string ret=s.substr(index_min,Maxlen);
return ret;
}
Manacher算法
Manacher算法的思路有点像dp，但比dp高明的多，它利用一个一维辅助数组L[i]，来求得以s[i]为对称中心的回文串长度。L[i]的含义是表述以s[i]为对称中心的最长回串的最右边到s[i]的距离。如aabab，经过预处理后变成#a#a#b#a#b#,那么可得如下的L数组：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| % | # | a | # | a | # | b | # | a | # | b |
| 0 | 0 | 1 | 2 | 1 | 0 | 3 | 0 | 3 | 0 | 1 |
我们发现：当L[i]就是以s[i]为对称中心的最长回文子串。
证明：首先在转换得到的字符串T中，所有的回文字串的长度都为奇数，那 么对于以T[i]为中心的最长回文字串，其长度就为2*Len[i]-1,经过观察可知，T中所有的回文子串，其中分隔符的数量一定比其他字符的数量多 1，也就是有Len[i]个分隔符，剩下Len[i]-1个字符来自原字符串，所以该回文串在原字符串中的长度就为
Len[i]-1。这里我们对内部的数组预先-1，那么回文串长度就是L[i]
构造L[i]
Manacher最重要的思想上面已经提到，利用L[i]能够的推出回文串，那么最重要的如何去快速的构造L[i]，最好以\(O(n)\)的方式。
为了降低复杂度，Manacher利用前面已经求好的L[0:i-1].同时维护两个值r和k来求出下一个L[i]，这也是为啥说Manacher也有dp的味道。因此最重要的三个元素：
- 假定要求位置\(i\)，那么i之前的记录已经求出并存储在L中
- 还有维护两个遍历
r和k。其中r表示，i之前所有位置求出来到右端点的最大值（即L数组的最大值对应的下标），k表示r最大时所在的位置
有了这些前提条件后，可以分为以下情况讨论：
\(i<r\)时，说明目前所求\(L[i]\)在以\(s[k]\)为对称中心的回文串内，我们就可以利用已有记录去求\(L[i]\)。找到
i关于k的对称点\(j=k-(i-k)=2k-i\)。比较\(L[j]\)与\(r-i\)的关系- \(L[j]<r-i\)：说明\(L[j]\)的回文串在\(L[k]\)内，由对称性推导就可以知道\(L[i]=L[j]\)。如下图：
- \(L[j]>=r-i\)：说明\(L[j]\)的一部分回文串在\(L[k]\)内，但超出的部分无法知道，需要一一暴力匹配，如下图：
- \(L[j]<r-i\)：说明\(L[j]\)的回文串在\(L[k]\)内，由对称性推导就可以知道\(L[i]=L[j]\)。如下图：
\(i>=r\)时，说明目前所求\(L[i]\)不在以\(s[k]\)为对称中心的回文串内，因此需暴力匹配
注意：记得在这个过程中更新k,r的值。
一些技巧：可以在字符串首尾放置两个"哨兵"，它们和其他字符串均不同，这样暴力更新时不用考虑边界问题，如用%和@取代#
代码实现
1 | string longestPalindrome(string s) { |
