LeetCode HOT100 - 回文子串

想到使用 manacher

先放代码，板子来自蒋老师，https://chuna2.787528.xyz/WIDA/p/17633758.html#马拉车manacher

std::vector<int> manacher(std::string s) {
    std::string t = "#";
    for (auto c : s) {
        t += c;
        t += '#';
    }
    int n = t.size();
    std::vector<int> r(n);
    for (int i = 0, j = 0; i < n; i++) {
        if (2 * j - i >= 0 && j + r[j] > i) {
            r[i] = std::min(r[2 * j - i], j + r[j] - i);
        }
        while (i - r[i] >= 0 && i + r[i] < n && t[i - r[i]] == t[i + r[i]]) {
            r[i] += 1;
        }
        if (i + r[i] > j + r[j]) {
            j = i;
        }
    }
    return r;
}

首先核心要求的就是 r[i] ，表示在变换后的串 t 中，以 i 为中心，最长能扩展出的回文半径

板子的开头是对字符串进行处理

主循环中，i 是当前要求的中心，j 是“当前最优中心”，即 它对应的回文向右延伸得最远

        while (i - r[i] >= 0 && i + r[i] < n && t[i - r[i]] == t[i + r[i]]) {
            r[i] += 1;
        }

这部分是好理解的，就是逐个判断当前中心能不能继续往外延展了

关键是

if (2 * j - i >= 0 && j + r[j] > i) {
    r[i] = std::min(r[2 * j - i], j + r[j] - i);
}

这也是保证复杂度的核心部分

2 * j - i 是指 i 关于 j 的镜像点，之所以要这个点是因为如果 i 落在以 j 为中心的那个大回文内部，那么根据回文对称性：i 附近的一部分回文信息，可以直接从 mirror 那里得到，进而可以少计算一些信息

而 j + r[j] 就是 j 对应的大回文右边界，因为当前点 i 落在以 j 为中心的那个“已知最右回文”内部才能像上面说的那样借用已有的信息

更新时就是对应点的半径信息和右边界到 i 距离的较小者

这样赋了初值后再暴力更新

最后再判断最优边界在这轮后有没有被刷新

对于这道题，使用板子的时候，就是要从 r[i] 出发求原串最长回文子串长度
在这种插 # 的写法下：原串中的最长回文长度 = max(r[i] - 1)

因为：

• 在变换串中半径包含了分隔符
• 去掉这些影响后，原串长度正好是 r[i] - 1

例如：

• "aba" 的中心半径 r = 4（变换后是 "#a#b#a#" ）
• 原串回文长度就是 4 - 1 = 3（注意是从半径到长度）
• "abba" 变换后对应中心也会有 r = 5
• 原串长度就是 5 - 1 = 4

int ans = 0;
for (int i = 0; i < r.size(); i++) {
    ans = std::max(ans, r[i] - 1);
}

于是完整代码就是

std::vector<int> manacher(std::string s) {
    std::string t = "#";
    for (auto c : s) {
        t += c;
        t += '#';
    }
    int n = t.size();
    std::vector<int> r(n);
    for (int i = 0, j = 0; i < n; i++) {
        if (2 * j - i >= 0 && j + r[j] > i) {
            r[i] = std::min(r[2 * j - i], j + r[j] - i);
        }
        while (i - r[i] >= 0 && i + r[i] < n && t[i - r[i]] == t[i + r[i]]) {
            r[i] += 1;
        }
        if (i + r[i] > j + r[j]) {
            j = i;
        }
    }
    return r;
}

class Solution {
public:
    int countSubstrings(string s) {
        auto r = manacher(s);
        int ans = 0;
        for (int i = 0; i < r.size(); i++) {
            ans += max(0, (r[i] - 1 + 1) / 2);
        }
        return ans;
    }
};