hdu 4513 吉哥系列故事——完美队形II (回文串,manacher)

题目链接:hdu4513

题意:给出一个n的数的序列,求出一个最长的回文字串,并且满足从[l,mid]单调增(非严格单调,可以相等),[mid,r]单调减(同样是可以相等)

思路:manacher…int型的也是可以搞的。。要求单调的话。。。while扩展的时候判一下就好了。。。

 

poj 3294 Girls’ research (manacher,回文串)

poj 3294
题意:先做个简单替换,然后求替换后的字符串的最长回文串,以及这个最长回文串的开始和结束位置。
思路:manacher..需要注意的是,返回下标的时候如果字符串长度为偶数,那么中间是没有字符的。。。需要特判一下。。(我的做法是left+(ans%2==0);

 

 

 

poj 3974 Palindrome (最长回文字串,manacher裸题)

poj3974
题意:求最大长度的回文字串。
思路:manacher裸题,用来练习算法。

hdu 3068 最长回文(O(n)求回文串,manacher算法模板题)

题目链接
题意:求一个字符串中的最长回文串。
思路:昨天武大校赛遇到了一个manacher算法的题。。。我竟然听都没听过。。。

于是去学习了一发。

感觉这篇博客讲得最详细manachar算法学习

于是切了个模板题练手。

先简单说下我对这个算法的理解,等做一些题目以后再来总结一发。
我觉得manachar算法最关键的一点是,如果你枚举回文串的中心位置,当你枚举到i的时候,那么i之前的位置回文串长度的最大值是已经确定的了。
换句话说,后面的中心位置不会影响前面的中心位置的答案。
于是可以利用前面已经做过的匹配来获得一些信息,避免了重复。
不过讲真。。。O(n)的复杂度。。这算法还是相当让人感到震撼的。。。
更具体的部分见代码注释。。。