manacher算法

Manacher 算法快速入门

Manacher 算法是一种用于寻找字符串中最长回文子串的高效算法，时间复杂度为 O(n)。

---

基本概念

回文

回文是一个字符串，从左到右和从右到左读都一样。

示例：

• 回文："aba"、"abba"
• 非回文："abc"、"abcd"

算法目标

给定字符串 s，找到其最长回文子串。

输入："babad"
输出："bab" 或 "aba"

---

算法思想

1. 字符串预处理：

   • 为了统一奇数和偶数长度的回文形式，插入分隔符 #。
   • 例如："babad" → "#b#a#b#a#d#"。

2. 维护变量：

   • P[i]：记录以位置 i 为中心的回文半径。
   • C：当前回文的中心。
   • R：当前回文的右边界。

3. 扩展回文并优化：

   • 对每个字符尝试扩展，并利用对称性优化。

4. 提取结果：

   • 根据 P 数组找到最大值，从而还原最长回文子串。

---

详细步骤

Step 1: 字符串预处理

通过插入 #，将奇数和偶数回文统一。

原始字符串："babad"
预处理后："#b#a#b#a#d#"

Step 2: 遍历字符串并更新

初始化 P 数组，按以下规则遍历：

1. 对称性优化：
   • 若 i 在右边界内：
     [
     P[i] = \min(P[\text{mirror}], R - i)
     ]
   • 对称点：mirror = 2C - i
2. 尝试扩展：
   • 在 t[i + P[i] + 1] == t[i - P[i] - 1] 条件下，扩展 P[i]。
3. 更新中心和右边界：
   • 如果扩展后的回文超出当前右边界，则更新 C 和 R。

Step 3: 提取最长回文

在 P 数组中找到最大值 P[i]，其对应的中心点 i 即为最长回文的中心。

利用公式：
[
\text{start} = \frac{\text{中心索引} - \text{半径}}{2}
]
将索引映射回原字符串，提取子串。

---

其中最关键的是关于中心 C 这个对称点的理解

比如 #a#b#a#b#a#c#
#a#b#a 对应 为 0 1 0 3 0 5
这时候 因为 最后一个字符的半径最大 这时候 找下一个字符的时候， 中心点就是 长度为5 的这个a

之后后面查找的时候， 就可以知道， 这个半径内， 左右是一样的， 那就可以快速跳过重复的查找

C++ 实现代码

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>using namespace std;string manacher(const string &s) {// 步骤 1: 预处理字符串，在每个字符两侧插入分隔符('#')string t = "#";for (char c : s) {t += c;t += "#";}int n = t.size();vector<int> P(n, 0); // 数组 P 存储以每个位置为中心的回文半径int C = 0, R = 0;    // 当前回文的中心 C 和右边界 R// 步骤 2: 遍历预处理后的字符串for (int i = 0; i < n; ++i) {// i 关于中心 C 的对称点int mirror = 2 * C - i;// 如果 i 在当前回文右边界内，初始化 P[i]if (i < R) {P[i] = min(P[mirror], R - i);}// 尝试扩展以 i 为中心的回文while (i + P[i] + 1 < n && i - P[i] - 1 >= 0 && t[i + P[i] + 1] == t[i - P[i] - 1]) {++P[i];}// 如果回文扩展超出当前右边界，更新中心 C 和右边界 Rif (i + P[i] > R) {C = i;R = i + P[i];}}// 步骤 3: 找到 P 数组中最大值，确定最长回文int max_len = 0, center_index = 0;for (int i = 0; i < n; ++i) {if (P[i] > max_len) {max_len = P[i];center_index = i;}}// 步骤 4: 从原始字符串中提取最长回文子串int start = (center_index - max_len) / 2; // 将索引从预处理后的字符串转换回原始字符串return s.substr(start, max_len);
}int run() {string s;cin >> s;string longest_palindrome = manacher(s);cout << "最长回文子串: " << longest_palindrome << endl;return 0;
}int main() {// 如果在苹果或Windows系统上，重定向输入输出
#if defined(__APPLE__) || defined(__WIN32__ )freopen("./slyar.in", "r+", stdin); // 重定向标准输入到slyar.in文件freopen("./slyar.out", "w+", stdout); // 重定向标准输出到slyar.out文件
#endifrun(); // 调用运行主逻辑函数
}