1回答

liuyubobobo

2021-09-15

manacher algorithm 是一个无论面试，升学，考研，考博，都肯定不会考的算法。甚至在大多数算法书中根本没有的算法。

但如果你对此感兴趣，这篇文章是我认为讲 manacher 讲的最好的文章：https://oi-wiki.org/string/manacher/

几点提示：

1）描述性文字看不懂的时候，请结合下面的代码看。看这段计算 d1 的代码就好：

d2 和 d1 大同小异。代码非常短，和看所有算法代码一样，一定要理解每个变量到底在代表什么。每一个自过程或者每一句话的用以到底是什么。

2）整个算法的核心是，保持存储着当前找到的最靠右的回文串。注意，不是最长的回文串，是最靠右的回文串。（l, r）存储。理解这一点是这个算法的关键。再强调：(l, r) 是已经找到的最靠右，最靠右，最靠右的回文串。

3）整个算法的思路和 z-algorithm 的思路很像。如果你学习过 z-algorithm，理解起来会很容易。但 z-algorithm 也是一个无论面试，升学，考研，考博，都肯定不会考的算法。甚至在大多数算法书中根本没有的算法。所以你很有可能没有学过 z-algorithm。反向的，如果理解了这个 manacher 算法，如果感兴趣，可以找找 z-algorithm 的资料自学一下，体会一下这种思想的应用。

继续加油！：）

0

hiuyubobobo

回复

heixin_慕圣6334738

hp>这句话等价于 Java 中：int[][] dp = new int[n][n]。然后为所有的 dp[i][j] 赋上 -1。

我不确定你是否理解什么是记忆化搜索，如果理解的话，这个程序的 dfs(s, a, b, dp) 就是在判断 s[a...b] 是否是回文串。判断方法就是如果 s[a] == s[b] 的话，递归的看 s[a + 1...b-1] 是否是回文串。整个程序对所有的 s 的子串判断了是否是回文串，拿到最长的回文串即可。

由于 dfs 使用了记忆化搜索，不会做重复的搜索，整个程序的复杂度是 O(n^2) 的。

继续加油！：）

h021-09-20

共2条回复