Java 中的 Manacher 算法

Manacher 算法是一种众所周知的用于确定给定字符串中最长回文子串的方法。它由 Glenn K. Manacher 于 1975 年提出。该算法利用回文对称的概念，减少了查找最长回文子串所需的比较次数。

Manacher 算法是识别给定字符串中最长回文子串的一种高效方法。它通过利用回文的对称性来工作。

示例

假设我们有字符串 "abaxabaxabb"。我们可以通过在每对字符之间插入 "#" 字符来创建一个新字符串："a#b#a#x#a#b#a#x#a#b#b#"。然后我们可以按如下方式应用 Manacher 算法：

1. 初始化 center = 0 和 right = 0。
2. 初始化 p 为 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]。
3. 遍历新字符串中的每个位置 i
   1. 在 i = 0 时，p[0] = 0。
   2. 在 i = 1 时，p[1] = 1，center = 1，right = 2。
   3. 在 i = 2 时，p[2] = 0。
   4. 在 i = 3 时，p[3] = 3，center = 3，right = 6。
   5. 在 i = 4 时，p[4] = 0。
   6. 在 i = 5 时，p[5] = 1，center = 3，right = 6。
   7. 在 i = 6 时，p[6] = 0。
   8. 在 i = 7 时，p[7] = 1，center = 7，right = 8。
   9. 在 i = 8 时，p[8] = 0。
   10. 在 i = 9 时，p[9] = 1，center = 7，right = 10。
   11. 在 i = 10 时，p[10] = 2，center = 10，right = 12。
   12. 在 i = 11 时，p[11] = 0。
   13. 在 i = 12 时，p[12] = 1，center = 10，right = 14。
   14. 在 i = 13 时，p[13] = 0。
   15. 在 i = 14 时，p[14] = 1，center = 14，right = 16。
   16. 在 i = 15 时，p[15] = 0。
   17. 在 i = 16 时，p[16] = 1，center = 14，right = 18。
   18. 在 i = 17 时，p[17] = 0。
   19. 在 i = 18 时，p[18] = 0。
   20. 在 i = 19 时，p[19] = 0。
   21. 在 i = 20 时，p[20] = 0。
   22. 在 i = 21 时，p[21] = 0。
   23. 在 i = 22 时，p[22] = 0。
   24. 在 i = 23 时，p[23] = 0。
   25. 在 i = 24 时，p[24] = 0。
   26. 在 i = 25 时，p[25] = 0。
4. 找到 p 中的最大值索引，为 14。新字符串中最长的回文子串是 "a#b#a#x#a#b#a#x#a#b#a"，对应于原始字符串 "abaxabaxaba"。由于 "#" 字符仅为算法添加，我们可以移除它们并得到原始回文。

算法

1. 通过在原始字符串的每对字符之间插入特殊字符（例如 #）来创建一个新字符串。这确保了新字符串中的每个回文都具有奇数长度。
2. 初始化两个变量：Center 和 right。Center 代表我们迄今为止找到的回文的中心，right 代表该回文的最右边界。
3. 初始化一个数组 p，用于存储新字符串中每个位置的回文长度。最初，所有元素都设置为零。
4. 遍历新字符串中的每个位置。在每个位置 i，执行以下操作：a. 如果 i 小于 right，则将 p[i] 设置为 p[2 * center - i] 和 right - i 之间的最小值。我们可以重用先前发现的回文的信息来避免冗余工作。b. 尽可能地扩展以 i 为中心的子串，并相应地更新 p[i]。c. 如果此回文的右边界超出了当前 right 的值，则相应地更新 Center 和 right。
5. 找到 p 中的最大值索引。它代表了新字符串中最长回文的中心。
6. 使用 Center 和回文长度从原始字符串中提取相应的子串。

实施

文件名： ManachersAlgorithm.java

输出

baxabaxab

复杂度分析： Manacher 算法在长度为 n 的字符串中查找最长回文子串的时间复杂度为 O(n)。这是因为该算法只处理字符串中的每个字符一次，并为每个字符执行常数时间的操作。

该算法的空间复杂度也为 O(n)。这是因为该算法使用一个长度为 n 的数组来存储回文长度，以及一个长度为 2n+1 的 StringBuilder 对象来修改输入字符串。