algorithm - 在 O(n) 或 O(n log n) 中查找回文子串的数量？

Question

我知道您可以使用 manacher 算法在 O(n) 中找到最长的回文子串，但是是否有可能在 O(n) 或 O(n log n)?如果是这样，您会怎么做？

也将单个字母算作回文。

---

例如，“xyxyx”的回文子串数为9。

这是因为你有:

5 single letter palindromes (x,y,x,y,x)
3 palindromes with three letters (xyx, yxy, xyx)
1 palindrome with five letters (xyxyx)

for a total of 5+3+1 = 9 palindromic substrings.

Answer 1

字符串 S 的子字符串 S' 是半径为 i 的最大回文当且仅当从中间开始它在两个字符串中读取相同i 个字符的方向，但不是 i+1 个字符的方向。

字符串中的任何回文都必须是具有相同中心的最大回文的子串。反之，具有相同中心的最大回文的每个子串也一定是回文。我们还可以很容易地计算具有相同中心的子回文的数量:长度为 k 的回文包含 Ceiling(k/2) 个。

鉴于我们可以使用 Manacher 算法在线性时间内找到所有最大回文，我们有一个线性时间算法来解决您的问题:找到最大回文的长度数组，除以二，取上限，对数组求和。

示例 1:在“xyxyx”上，最大回文数是

x, xyx, xyxyx, xyx, x

和Manacher的可以用来计算一个数组

1, 0, 3, 0, 5, 0, 3, 0, 1

表示以每个字母和字母之间的每个间隙为中心的最大回文的长度。无论如何，将 map Ceiling(k/2) 应用于条目，我们得到

1, 0, 2, 0, 3, 0, 2, 0, 1

总和为 9。

示例 2:“abba”。最大回文是

a, b, abba, b, a

Manacher的可以用来获取数组

1, 0, 1, 4, 1, 0, 1

Ceiling(k/2)数组是

1, 0, 1, 2, 1, 0, 1

总和为 6(a、b、b、a、bb、abba)。