Manacher算法通过预处理将字符串统一为奇数长度回文，利用对称性和已知回文半径数组P，在O(n)时间内求出最长回文子串；遍历中维护最右边界right和中心center，借助mirror减少重复扩展，最后根据P数组最大值定位原串起始位置并返回结果。
Manacher算法能在O(n)时间内找出字符串中最长回文子串，比暴力和动态规划更高效。C++实现的关键是预处理字符串并维护回文半径数组。
预处理字符串
在原字符串每个字符间插入特殊符号（如’#’），并在首尾添加不同边界符，避免越界。例如 “aba” 变为 “^#a#b#a#$”。
这样做可以把奇偶长度回文统一处理，所有回文都变为奇数长度。
维护回文半径数组 P
定义数组 P[i] 表示以位置 i 为中心的最长回文半径（不包含中心）。同时维护最右回文边界 right 和对应中心 center。
立即学习“C++免费学习笔记（深入）”；
遍历每个位置 i：
如果 i 在 right 内，利用对称性：P[i] = min(right – i, P[2 * center – i])尝试向外扩展，更新 P[i]如果 i + P[i] > right，更新 center 和 right
提取最长回文
扫描 P 数组找到最大值及其位置，再映射回原字符串。
原串中起始位置为 (maxCenter – maxLen) / 2，长度为 maxLen。
以下是一个完整可运行的 C++ 实现：
#include #include #include using namespace std;string longestPalindrome(string s) { if (s.empty()) return ""; // 预处理字符串 string transformed = "^#"; for (char c : s) { transformed += c; transformed += '#'; } transformed += '$'; int n = transformed.size(); vector P(n, 0); int center = 0, right = 0; for (int i = 1; i < n - 1; i++) { int mirror = 2 * center - i; if (i right) { center = i; right = i + P[i]; } } // 找最长回文 int maxLen = 0, maxCenter = 0; for (int i = 1; i maxLen) { maxLen = P[i]; maxCenter = i; } } int start = (maxCenter - maxLen) / 2; return s.substr(start, maxLen);}// 测试int main() { string s = "babad"; cout << longestPalindrome(s) << endl; // 输出 bab 或 aba return 0;}
基本上就这些。核心是利用已知回文的对称性减少重复计算，达到线性时间复杂度。
以上就是C++怎么实现Manacher算法_C++在线性时间内查找最长回文子串的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1486096.html
微信扫一扫 
支付宝扫一扫 
