最长回文子串

回文字符串

如果一個長度為  的字符串  當中所有字符依次為 . 且  滿足 , 那麼則稱  為一個回文字符串。

最長回文子串

如果字符串  的一個回文子串  是  所有回文子串中長度最長的，那麼則稱  為  的最長回文子串。

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