首页 > 代码库 > HDU 3068 最长回文 Manacher算法
HDU 3068 最长回文 Manacher算法
Manacher算法是个解决Palindrome问题的O(n)算法,可以说是个超级算法了,秒杀其他一切Palindrome解决方案,包括复杂的后缀数组。
网上很多解释,最好的解析文章当然是Leetcode的了:http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html
这里总结一下思想重点:
1 原字符串的字符间插入新的字符, 如#,方便统一所有的字符中心,比如aa和aba的字符中心不一样的,aa的字符中心可以说是aa,而aba的中心则是b,而插入#之后,aa成#a#a#,其中心是一个字符#,而aba插入#a#b#a#,中心还是一个字符b。
2 充分利用前面已经计算出的信息来计算后面的信息,这里主要利用palindrome的对称性的特性,那么就可以利用对称中心前半段的信息计算后半段的信息了。这个是优化算法到O(n)的关键。 因为对称中心是不断右移的,故此在对称中心内的求解只需直接copy前半段的信息就可以,而超出当前对称范围的就需要expand Palindrome了。
3 防止溢出,前面加一个额外的特殊字符,如‘~‘,和前面的插入字符不一样。后面也需要插入字符,但是为什么很多程序不插入字符呢?那是因为C++的char都是以‘\0‘结束的,故此,不插入也是可以的,下面程序明显插入‘\0‘到结尾了。
4 需要维护最右点信息,中心信息和P数组,P数组的含义是以i点为中心的最长palindrome子字符串的长度,这里是长度+1,方便计算。
关键代码就几行,但是思想却是十分难的。
#include <stdio.h> #include <string.h> const int MAX_2L = 220010; char txt[MAX_2L]; int P[MAX_2L]; int len; inline int min(int a, int b) { return a < b? a : b; } inline int max(int a, int b) { return a > b? a : b; } void preProcess() { len = strlen(txt); int i = len-1, j = (len<<1); txt[j+2] = '\0'; txt[j+1] = '#'; for ( ; i >= 0; i--) { txt[j--] = txt[i]; txt[j--] = '#'; } txt[0] = '~'; } int main() { while (gets(txt)) { preProcess(); len = len << 1 | 1; int maxLen = 0, right = 0, center = 0; for (int i = 1; i <= len; i++) { P[i] = i<right ? min(P[(center<<1)-i], right-i) : 1; while (txt[i-P[i]] == txt[i+P[i]]) P[i]++; maxLen = max(maxLen, P[i]); if (right < i+P[i]) center = i, right = i+P[i]; } printf("%d\n", maxLen-1); gets(txt); //get rid of empty line } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。