最长回文子串

最长回文子串（英語：Longest palindromic substring）是计算机科学中的問題，在一个字符串中查找一个最长的连续的回文的子串，例如“banana”最长回文子串是“anana”。最长回文子串并不一定是唯一的，比如“abracadabra”，没有超过3的回文子串，但是有两个回文字串长度都是3：“ada”和“aca”。在一些应用中，我们求出全部的极大回文子串（不被其他回文串包含的回文子串）。

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

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

定义

回文字符串

如果一个长度为 $n$ 的字符串 $s$ 当中所有字符依次为 $s_{0},\,s_{1},\,s_{2}\,\cdots \,s_{n-1}$. 且 $s$ 满足 $\forall i\in \left[0,\left\lfloor {\frac {n}{2}}\right\rfloor \right],\;s_{i}=s_{n-i-1}$, 那么则称 $s$ 为一个回文字符串。

最长回文子串

如果字符串 $s$ 的一个回文子串 $s_{1}$ 是 $s$ 所有回文子串中长度最长的，那么则称 $s_{1}$ 为 $s$ 的最长回文子串。

Manacher算法

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

1. 回文的左边是右边的镜像
2. （情况1）如“dacabacad”中有三个回文。整体是第一个，左侧“aca”是第二个，右侧“aca”是三个。可总结规律：如果一个回文串中有三个回文子串（包括自身），且小回文串没有触碰到大回文的边界，那么其中两个小回文串长度相等。
3. （情况2）接上文，如果左侧小回文串触碰或超越大回文边界，那这个左侧小回文中心到大回文的左边界，等于右侧小回文中心到大回文的右边界。
4. 为了计算右侧小回文的长度（对于情况2），大回文串右侧边界的下一个元素应该和其与右侧小回文串中心对称的元素比较。直到不匹配为止。
5. （情况3）若有一个回文子串的中心在大回文串外，那么现有的3个回文子串无法判断第4回文串的位置。
6. 因此有回文串参照的情况比较理想（大回文串即为很好的参照）。情况2中的右侧回文串和情况3中的第四回文串可以代替原有大回文串。
7. 复杂度计算：情况1不需要比较，情况2、3只需比较右侧最外侧元素和其与当前参照回文串的对称元素。情况3会返回一个新的参照物，而情况2只有在右侧回文串比左侧对应回文串长时才会产生新的参照。
8. 对于偶数长度的回文，回文中心在中间两个字母之间。

实现

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;
    }