马拉车

Manacher

O(n)O(n) 时间复杂度下解决回文子串问题

将原字符串的所有空隙（包括头尾）插入 【#】，保证每个回文子字符串都为奇数。

现在仅考虑奇数回文串的计算：

记 dp[i] 为以 i 为中心的最长回文串半径（包括 i，如对于 ababa，dp[2] = 3）

  1. 记录当前回文字符串最远的右边界及其对应的左边界，记为 l，r。（初始化 l = 0, r = -1）
  2. 遍历到 s[i] 时，考虑 s[i] 是否在 l~r 范围内
    1. i > r，无法根据前面的数据计算回文串，只能退化为最朴素的中心扩散法。
    2. i <= r，考虑 i 在 [l:r] 中的翻转结果 j，即 j = l + r - i，由于回文串的性质，在 [l:r] 范围内，以 j 为中心的回文串长度等于以 i 为中心的回文串长度。
      • 考虑到特殊情况，若 i 的回文串右端点能扩展到 r 之外，实际答案会大于 dp[j]，对于 r 之外部分的比较，仍采用朴素的中心扩散法。

在加入【#】 后，可以全部考虑成奇数回文串的计算。我们记实际字符串为 S，插入【#】之后的字符串为 SS，那么在 SS 中计算得到的 dp[i] 相当于其在 S 中对应位置的回文串长度 + 1。什么对应位置呢？即字母对应字母，# 对应字母间空格。

举例：ababac => #a#b#a#b#a#c#，#a#b#a#b#a# 对应 ababa，dp[i] = len(#a#b#a) = 6，实际长度 len(ababa) = 5

偶数情况同理：abbac => #a#b#b#a#c#，那么 #a#b#b#a# 对应 abba，dp[i] = len(#a#b#) = 5，实际长度 len(abba) = 4

TypeScript 
export function useManacher(s: string) {
    const char = new Array(s.length * 2 + 1)
    const n = char.length
    let i = 1
    char[0] = '#'
    for (const ch of s) {
        char[i++] = ch
        char[i++] = '#'
    }
    const dp: number[] = new Array(n).fill(0)
    for (let i = 0, l = 0, r = -1; i < n; i++) {
        let k = i > r ? 1 : Math.min(dp[l + r - i], r - i + 1)
        while (i - k >= 0 && i + k < n && char[i - k] === char[i + k]) k++

        dp[i] = k--

        if (i + k > r) {
            r = i + k
            l = i - k
        }
    }

    return dp
}
JavaScript 
export function useManacher(s) {
    const char = new Array(s.length * 2 + 1)
    const n = char.length
    let i = 1
    char[0] = '#'
    for (const ch of s) {
        char[i++] = ch
        char[i++] = '#'
    }
    const dp = new Array(n).fill(0)
    for (let i = 0, l = 0, r = -1; i < n; i++) {
        let k = i > r ? 1 : Math.min(dp[l + r - i], r - i + 1)
        while (i - k >= 0 && i + k < n && char[i - k] === char[i + k]) k++
        dp[i] = k--
        if (i + k > r) {
            r = i + k
            l = i - k
        }
    }
    return dp
}
Java 

class Manacher {

    public static int[] manacher(String s) {
        char[] c = new char[s.length() * 2 + 1];
        int n = c.length, _i = 1;
        c[0] = '#';
        for (char ch : s.toCharArray()) {
            c[_i++] = ch;
            c[_i++] = '#';
        }
        int[] dp = new int[n];
        for (int i = 0, l = 0, r = -1; i < n; i++) {
            int k = i > r ? 1 : Math.min(dp[l + r - i], r - i + 1);
            // 朴素的中心扩散法
            while (0 <= i - k && i + k < n && c[i - k] == c[i + k]) {
                k++;
            }
            dp[i] = k--;
            // 更新 l,r
            if (i + k > r) {
                r = i + k;
                l = i - k;
            }
        }
        return dp;
    }
    // 实际情况长度 = dp[i] - 1
    /*
     * 求最长回文子串：
     * for (int d : dp) res = Math.max(res, d - 1);
     */

 /*
     * 求所有回文串个数：
     * for (int d : dp) {
     * int t = d - 1;
     * res += t / 2 + t % 2;
     * }
     */
}