Manacher算法
Manacher算法是一个用来求解最长回文子串(Longest Palindromic Substring)的高效算法。其核心是在枚举回文字串的中心位置，并在计算其对应的回文子串时充分前 面的已经算出来的结果。
算法原理
首先，需要考虑回文子串长度为奇数和为偶数的情形下的差异，为了消除这一差异，在长度为n的字符串中插入 $n+1$ 个无关字符，例如’#’,’*‘等。这一步骤时间复杂度为 $O(n)$。 Manacher算法需要 $O(n)$ 的辅助数组，用来记录每一个位置可以向右扩展回文串的长度（包含其自身），同时，记录当前有最大向右扩展长度的索引位置 $id$，那么， 辅助数组有如下性质：
if(f[id] + id > i)
f[i] = min(f[2*id-i], f[id]+id-i)
解释：$2*id-i$ 为 $i$ 关于 $id$ 位置的对称位置，在考虑回文串长度时，$i$ 位置能够向右扩展的长度应不小于 $j$ 位置向左扩展的长度，而以 $j$ 为中心位置的 回文串的左右扩展长度相同。同时，如果 $i$ 在 $id$ 的扩展范围内，在 $i$ 位置未单独向右扩展之前，$i$ 位置能够向右扩展的位置应当小于 $id$ 向右扩展的位置。
在找到 $f[i]$ 的下界后，开始以 $i$ 为中心，$f[i]$ 为长度下界，扩展此回文串。具体做法如下：
while(str[i-f[i]] == str[i+f[i]])
f[i]++
找到i位置能够扩展的最大长度之后，如果i位置能够向右到达的最大位置大于 $id$ 位置能够向右到达的最大位置，则更新 $id$。
最后，由于之前已经在每两个字符之间插入了无关字符，因此，以 $i$ 为中心位置的最长回文字串的长度为 $f[i]-1$,线性扫一遍，便可以得到该字符串的最大回文字串 长度。
复杂度解释
由于每次最外层循环都在扩展能够向右到达的最大位置，而该位置值的最大值为字符串的长度，因此，此算法具有 $O(n)$ 的优异复杂度。
参考题目
http://hihocoder.com/problemset/problem/1032
题解：
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
// manacher.
int len, f[2000010];
char str[2000010];
int solve()
{
int id = 0, mx = 0, ans = 0; // mx = id + f[id]
memset(f, 0x00, sizeof(f));
for (int i = 1; i <= 2 * len; ++i) {
if (mx > i) {
f[i] = min(f[2 * id - i], f[id] + id - i);
} else {
f[i] = 1;
}
while (i-f[i] >= 0 && i+f[i] <= 2*len && str[i+f[i]] == str[i-f[i]]) {
f[i]++;
}
if (f[i] + i > mx) {
mx = f[i] + i;
id = i;
}
if (str[i] == '#') {
ans = max(ans, ((f[i]-1)/2) * 2);
} else {
ans = max(ans, ((f[i]-1)/2) * 2 + 1);
}
}
return ans;
}
int main(int argc, char **argv)
{
int n;
scanf("%d", &n);
while (n--) {
scanf("%s", str);
len = strlen(str);
// 预处理
for (int i =len-1; i >= 0; --i) {
str[2*i+1] = str[i];
str[2*i+2] = '#';
}
str[0] = '#';
printf("%d\n", solve());
}
return 0;
}
LeetCode OJ 005. Longest Palindromic Substring
class Solution:
# @param {string} s
# @return {string}
def longestPalindrome(self, s):
T = '#'.join('^{}$'.format(s))
n, p, c, r = len(T), [0]*len(T), 0, 0
for i in range(1, n-1):
p[i] = (r>i) and min(r-i, p[2*c-i])
while T[i+1+p[i]] == T[i-1-p[i]]:
p[i] += 1
if i+p[i] > r:
c, r = i, i+p[i]
maxlen, centerindex = max((n, i) for i, n in enumerate(p))
return s[(centerindex - maxlen)//2: (centerindex + maxlen)//2]
扩展
还有以下几种算法可以用来求解序列的最长回文字串：
- 暴力法
枚举起点和终点，然后判断该字串是否为回文字串，时间复杂度 $O(n^3)$。
- 动态规划
原理：最长回文字串的字串也是回文的，因此可以将最长回文字串分解为一系列的子问题。需要额外的 $O(n^2)$ 的空间，时间复杂度也为 $O(n^2)$。
定义 $P[i][j]=1$ 表示 $S[i][j]$ 是回文字符串，若为 $0$，则不是。那么，状态转移方程为：
\[p_{i,j} = \begin{cases} 0 & {i = j} \text{ (initial)} \\ p[i+1][j-1] & {s_i = s_j} \\ 0 & {s_i \neq s_j} \end{cases}\]算法实现：
string findLongestPalindrome(string &s) {
const int length = s.size();
int start, maxlength = 0;
bool P[50][50] = {false};
for(int i = 0; i < length; i++) { //初始化准备
P[i][i] = true;
if(i < length-1 && s.at(i) == s.at(i+1)) {
P[i][i+1] = true;
start = i; maxlength = 2;
}
}
for(int len=3; len<length; len++) { //子串长度
for(int i=0; i<=length-len; i++) { //子串起始地址
int j=i+len-1; //子串结束地址
if(P[i+1][j-1] && s.at(i)==s.at(j)) {
P[i][j]=true;
start = i; maxlength=len;
}
}
}
if(maxlength>=2) {
return s.substr(start,maxlength);
}
return NULL;
}
- 中心扩展
中心扩展就是把给定的字符串的每一个字母当做中心，向两边扩展，这样来找最长的子回文串。算法的时间复杂度为 $O(N^2)$。但是要考虑两种情况：
- 例如”aba”，这样长度为奇数。
- 例如”abba”，这样长度为偶数。
这一方法的优点在于实现简单：
string findLongestPalindrome(string &s) {
const int length = s.size();
int start, maxlength=0;
for(int i=0; i<length; i++) { //长度为奇数
int j=i-1, k=i+1;
while(j>=0 && k<length && s.at(j)==s.at(k)) {
if(k-j+1>maxlength) {
maxlength=k-j+1; start=j;
}
j--; k++;
}
}
for(int i=0; i<length; i++) { //长度为偶数
int j=i, k=i+1;
while(j>=0 && k<length && s.at(j)==s.at(k)) {
if(k-j+1>maxlength) {
maxlength=k-j+1; start=j;
}
j--; k++;
}
}
if(maxlength > 0) {
return s.substr(start,maxlength);
}
return NULL;
}
- 后缀数组
还可以利用后缀数组等其他算法解决最长回文子串问题，但时间复杂度和编程复杂度均高于Manacher算法。