Manacher 算法(马拉车算法)
2022/1/25 20:06:45
本文主要是介绍Manacher 算法(马拉车算法),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
参考博客
该算法可以在时间空间都为O(n),求出最大的回文子串
string longestPalindrome(string s) { string str; string ans; int start=0, end=0; str += "$#"; for (int i = 0; i < s.size(); i++) {//初始化,使用#对字符串每一个间隙都进行填充 str += s[i]; str += "#"; } str += "^";//字符串首尾加上#,^不同字符避免越界判定 int len = str.size(); int Max_len = -1;//最大的回文长度 int id;//最右边的回文串的最中间 int mx = 0;//最右边的回文串的最右界限 int p[2009] = {}; for (int i = 1; i < len; i++) { if (i < mx) {//在界限内 p[i] = min(p[2 * id - i], mx - i); } else { p[i] = 1; } while (str[i - p[i]] == str[i + p[i]]) {//扩大 p[i]++; } if (mx < i + p[i]) {//如果不是最右,更新 id = i; mx = i + p[i]; } if (p[i] - 1 > Max_len) {//记录位置 Max_len = p[i] - 1; start = i - p[i]+1; end = i + p[i]-1; } } for (int i = start; i <= end; i++) {//截取最大回文串 if (str[i] != '#') { ans += str[i]; } } return ans; } int main() { cout << longestPalindrome("babad") << endl;//bab return 0; }
这篇关于Manacher 算法(马拉车算法)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享
- 2024-09-28Kotlin的stateFlow.update 写法介绍-icode9专业技术文章分享
- 2024-09-28kotlin 怎么获取当前时间格式-icode9专业技术文章分享