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

Question

我知道你可以找到最长的回文子在O(N)与manacher的算法,但有可能找到的总人数在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是半径的最大回文iiff,从中间开始,它在i字符的两个方向上读取相同,但不是i+1字符.

字符串中的任何回文必须是具有相同中心的最大回文的子串.相反,具有相同中心的最大回文的每个子串也必须是回文.我们也可以很容易地计算具有相同中心的副回文数:长度k包含Ceiling(k/2)它们的回文.

鉴于我们可以在线性时间内使用Manacher算法找到所有最大回文,我们为您的问题提供线性时间算法:找到最大回文长度数组,除以2,取上限,求数组.

实施例1:在"xyxyx"上,最大回文是

x, xyx, xyxyx, xyx, x

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

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

表示以每个字母为中心的最大回文长度和字母之间的每个间隙.无论如何,将地图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)'d数组是

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

总和为6(a,b,b,a,bb,abba).