111qqz的小窝

老年咸鱼冲锋!

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

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

于是去学习了一发。

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

于是切了个模板题练手。

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

说点什么

您将是第一位评论人!

提醒
wpDiscuz