Manacher

· · 算法·理论

问题 给定字符串 S,对每个 i 求出最长回文半径 d_i。

顺序扫描 i =1\to n,维护 [l,r] 为覆盖当前 i 的最长回文区间。根据回文串对称性分讨:

求出 i 后对应更新 [l,r]。复杂度均摊线性。

void manacher() {
    for (int i = 1, l = 1, r = 0; i <= n; i++) {
        int k = i > r ? 1 : min(d[l+r-i], r-i+1);
        while (i-k >= 1 && i+k <= n && s[i-k] == s[i+k]) k++;
        d[i] = k--;
        if (i+k > r) l = i-k, r = i+k;
    }
}

上面的代码只能求奇回文串。偶回文串可以单独讨论,也可以将原串变为

{\tt{!\#}}S_1 {\tt{\#}} S_2 {\tt{\#}} \cdots S_n {\tt{\#}} {\tt{?}}

后转化为奇回文情形。

定理 本质不同回文子串至多 n 个。

更强的结论是,每加入一个 i,本质不同回文子串数至多 +1,且必然对应最长的那个子串。