Manacher 算法模板详解

靖2025-01-072025-01-07

Manacher 算法模板详解

1. 简介

Manacher 算法是一个用于在线性时间内求解字符串中所有位置的最长回文子串长度的算法。它通过巧妙地利用已计算的信息，避免了重复计算。

主要特点：

线性时间复杂度 O(n)
可以处理奇数和偶数长度的回文串
能找到所有位置的最长回文子串
实现简单，易于理解

2. 实现原理

2.1 基本概念

回文串：
- 正着读和倒着读都一样的字符串
- 可以是奇数或偶数长度
半径数组：
- 记录每个位置的回文半径
- 通过半径可以得到回文长度

2.2 核心策略

字符串预处理：
- 在字符间插入特殊字符（通常是#）
- 统一处理奇偶长度的回文串
中心扩展：
- 利用已知回文串的对称性
- 尽可能减少重复计算

3. 模板代码

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

4. 函数说明

4.1 参数说明

1	std::vector<int> manacher(std::string s)

s: 输入字符串
返回值：每个位置的回文半径数组

4.2 返回值解释

r[i]: 表示以位置i为中心的最长回文串的半径
实际回文串长度为 r[i] - 1

5. 时间复杂度分析

时间复杂度：O(n)
- 每个位置最多被扩展一次
- 利用对称性避免重复计算
空间复杂度：O(n)
- 需要存储处理后的字符串
- 需要存储回文半径数组

6. 应用场景

最长回文子串查找
回文子串计数
回文串相关动态规划
字符串处理和分析

7. 使用示例

7.1 查找最长回文子串

string longestPalindrome(string s) {
    auto r = manacher(s);
    string t = "#" + string(s.size() * 2, '#');
    for (int i = 0; i < s.size(); i++) {
        t[i * 2 + 1] = s[i];
    }
    
    int maxLen = 0, center = 0;
    for (int i = 0; i < t.size(); i++) {
        if (r[i] - 1 > maxLen) {
            maxLen = r[i] - 1;
            center = i;
        }
    }
    
    string res;
    for (int i = center - r[center] + 1; i < center + r[center]; i++) {
        if (t[i] != '#') res += t[i];
    }
    return res;
}

7.2 统计回文子串个数

int countPalindromes(string s) {
    auto r = manacher(s);
    int count = 0;
    for (int i = 0; i < r.size(); i++) {
        count += (r[i] - 1) / 2;
    }
    return count;
}