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)

解释:2idii 关于 id 位置的对称位置,在考虑回文串长度时,i 位置能够向右扩展的长度应不小于 j 位置向左扩展的长度,而以 j 为中心位置的 回文串的左右扩展长度相同。同时,如果 iid 的扩展范围内,在 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]

扩展

还有以下几种算法可以用来求解序列的最长回文字串:

  1. 暴力法

枚举起点和终点,然后判断该字串是否为回文字串,时间复杂度 O(n3)

  1. 动态规划

原理:最长回文字串的字串也是回文的,因此可以将最长回文字串分解为一系列的子问题。需要额外的 O(n2) 的空间,时间复杂度也为 O(n2)

定义 P[i][j]=1 表示 S[i][j] 是回文字符串,若为 0,则不是。那么,状态转移方程为:

pi,j={0i=j (initial)p[i+1][j1]si=sj0sisj

算法实现:

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;
}
  1. 中心扩展

中心扩展就是把给定的字符串的每一个字母当做中心,向两边扩展,这样来找最长的子回文串。算法的时间复杂度为 O(N2)。但是要考虑两种情况:

  • 例如”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;
}
  1. 后缀数组

还可以利用后缀数组等其他算法解决最长回文子串问题,但时间复杂度和编程复杂度均高于Manacher算法。

参考

  1. Longest palindromic substring