Manacher算法
Manacher算法是一个用来求解最长回文子串(Longest Palindromic Substring)的高效算法。其核心是在枚举回文字串的中心位置,并在计算其对应的回文子串时充分前 面的已经算出来的结果。
算法原理
首先,需要考虑回文子串长度为奇数和为偶数的情形下的差异,为了消除这一差异,在长度为n的字符串中插入
if(f[id] + id > i)
f[i] = min(f[2*id-i], f[id]+id-i)
解释:
在找到
while(str[i-f[i]] == str[i+f[i]])
f[i]++
找到i位置能够扩展的最大长度之后,如果i位置能够向右到达的最大位置大于
最后,由于之前已经在每两个字符之间插入了无关字符,因此,以
复杂度解释
由于每次最外层循环都在扩展能够向右到达的最大位置,而该位置值的最大值为字符串的长度,因此,此算法具有
参考题目
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]
扩展
还有以下几种算法可以用来求解序列的最长回文字串:
- 暴力法
枚举起点和终点,然后判断该字串是否为回文字串,时间复杂度
- 动态规划
原理:最长回文字串的字串也是回文的,因此可以将最长回文字串分解为一系列的子问题。需要额外的
定义
算法实现:
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;
}
- 中心扩展
中心扩展就是把给定的字符串的每一个字母当做中心,向两边扩展,这样来找最长的子回文串。算法的时间复杂度为
- 例如”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算法。