最长回文子串

维基百科,自由的百科全书
跳到导航 跳到搜索

在计算机科学中,最长回文子串或最长对称因子问题是在一个字符串中查找一个最长的连续的回文的子串,例如“banana”最长回文子串是“anana”。最长回文子串并不一定是唯一的,比如“abracadabra”,没有超过3的回文子串,但是有两个回文字串长度都是3:“ada”和“aca”。在一些应用中,我们求出全部的极大回文子串(不被其他回文串包含的回文子串)。

Manacher于[1]发现了一种线性时间算法,可以在列出给定字符串中从任意位置开始的所有回文子串。并且,Apostolico, Breslauer & Galil [2]发现,同样的算法也可以在任意位置查找全部极大回文子串,并且时间复杂度是线性的。因此,他们提供了一种时间复杂度为线性的最长回文子串解法。另外,Jeuring (1994)[3], Gusfield (1997)[4]发现了基于后缀树的算法。也存在已知的高效并行算法。

最长回文子串算法不应当与最长回文子序列算法混淆。

定义[编辑]

回文字符串[编辑]

如果一个长度为 字符串 当中所有字符依次为 . 且 满足 , 那么则称 为一个回文字符串。

最长回文子串[编辑]

如果字符串 的一个回文子串 所有回文子串中长度最长的,那么则称 的最长回文子串。

Manacher算法[编辑]

要在线性时间内找出字符串的最长回文子串,这个算法必须利用回文和子回文的这些特点和观察

  1. 回文的左边是右边的镜像

实现[编辑]

Python[编辑]

def manacher(s0 : str) -> list:
    T = '$#' + '#'.join(s0) + '#@'
    l = len(T)
    P = [0] * l
    R, C = 0, 0
    for i in range(1,l-1):
        if i < R:
            P[i] = min(P[2 * C - i], R - i)
        
        while T[i+(P[i]+1)] == T[i-(P[i]+1)]:
            P[i] += 1
        
        if P[i] + i > R:
            R = P[i] + i
            C = i
    return P

C++[编辑]

constexpr auto MAXN = (int)7000000;

char s[MAXN << 1], str[MAXN];
int RL[MAXN];

int Manacher(void) {
	size_t len = strlen(str); *s = '#';
	for (int i = 0; i < len; i++) {
		s[(i << 1) + 1] = str[i]; s[(i << 1) + 2] = '#';
	}len = (len << 1) + 1;

	int max = 1, pos, maxRight = -1; memset(RL, 0, sizeof(RL));
	for (int i = 0; i < len; i++) {
		if (i < maxRight) RL[i] = std::min(RL[(pos << 1) - i], maxRight - i);
		else RL[i] = 1;
		while (i - RL[i] >= 0 && i + RL[i] < len && s[i - RL[i]] == s[i + RL[i]])++RL[i];
		if (i + RL[i] > maxRight) { pos = i; maxRight = i + RL[i]; }
		max = std::max(max, RL[i] - 1);
	} return max;
}


Matlab[编辑]

function m = Manacher(a)
    T = ['$#' reshape([a;ones(size(a))*'#'], 1, '') '@'];
    l = length(T);
    P = zeros(1, l);
    
    mx = 0; %range
    id = 0; %center
    for i = 2:l-1
        if i < mx
            P(i) = min(P(2 * id - i), mx - i);
        else 
            P(i) = 1;
        end
        
        while T(i+P(i)) == T(i-P(i))
            P(i) = P(i) + 1;
        end
        
        if P(i) + i > mx
            mx = P(i) + i;
            id = i;
        end
    end
    m = max(P)-1;

Java[编辑]

    // 生成新的辅助String, eg: abc123成为#a#b#c#1#2#3#2#1#
    public static char[] manacherStringString(String str) {
        char[] c = str.toCharArray();
        char[] res = new char[c.length * 2 + 1];
        int index = 0;
        for (int i = 0; i != res.length; i++) {
            // 两个一样效果, 填充符号"#"
            res[i] = (i % 2) == 0 ? '#' : c[index++];
            // res[i] = (i & 1) == 0 ? '#' : c[index++];
        }
        return res;
    }

    // 返回最长回文串长度
    public static int maxLcpsLength(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        char[] charArr = manacherStringString(str);
        // 辅助回文长度数组, 表示最多能扩充多少
        int[] pArr = new int[charArr.length];
        // 中心点
        int C = -1;
        // 最右边界
        int R = -1;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i != charArr.length; i++) {
            // i在右边界内, i`到C的长度和到i到R的距离, 哪个小, 哪个就是起码成为回文的区域
            // 否则为1, 自身
            pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
            // 检查边界
            while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
                if (charArr[i + pArr[i]] == charArr[i - pArr[i]]) {
                    // 左右字母相等, 扩1, 直到不能扩为止
                    pArr[i]++;
                } else {
                    // 不能扩
                    break;
                }
            }
            // 如果大于R, 那更新回文右边界和中心点
            if ((i + pArr[i]) > R) {
                R = i + pArr[i];
                C = i;
            }
            // 如果需要, 则更新max
            max = Math.max(max, pArr[i]);
        }
        // 返回最大回文长度
        return max - 1;
    }

参考资料[编辑]

  1. ^ Manacher, Glenn. A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String. Journal of the ACM (JACM). 1975-07-01, 22 (3): 346–351. ISSN 0004-5411. doi:10.1145/321892.321896. 
  2. ^ Apostolico, Alberto; Breslauer, Dany; Galil, Zvi. Parallel detection of all palindromes in a string. Theoretical Computer Science. 1995-04, 141 (1-2): 163–173. ISSN 0304-3975. doi:10.1016/0304-3975(94)00083-u. 
  3. ^ Jeuring, Johan. The derivation of on-line algorithms, with an application to finding palindromes. Algorithmica. 1994-02, 11 (2): 146–184. ISSN 0178-4617. doi:10.1007/bf01182773 (英语). 
  4. ^ Gusfield, Dan. Algorithms on Strings, Trees, and Sequences. 9.2 Finding all maximal palindromes in linear time", Algorithms on Strings, Trees, and Sequences. Cambridge: Cambridge University Press. 1997. ISBN 9780511574931. doi:10.1017/cbo9780511574931 (英语).