计算O(n)中的回文子串

Question

给定S长度的字符串(假设只有英文字符)n,我们可以使用以下算法计算回文子串的数量:

for i = 0 to |S| do
    p1 = number of palindromes centered in i (odd length)
    p2 = number of palindromes centered in i and i+1 (even length)

    add p1 + p2 to total number of palindromic substrings of S

O(n^2)但是,上面的代码.

我对解决这个问题的算法很感兴趣O(n).我肯定知道一个存在,因为我听到多个人说它确实存在,并且问题存在于一个上限为1 000 000on 的本地在线评判网站上n,但我从未见过算法,似乎无法能够想出来.

更新:

我的一般想法是len[i] = length of the longest palindrome centered at the character 2i + 1为偶数长度的回文计算和类似的数组.通过良好的簿记,应该可以O(1)为每个角色计算这一点,这将使我们能够同时计算大量的回文.然而,我仍然坚持如何计算这一点.

我会接受一个使用O(n)甚至可能是O(n log n)额外内存的解决方案.我想如果没有它,这是不可能的.

任何好的想法或参考都表示赞赏.

Answer 1

以下站点显示了在O(n)时间内计算最长回文子串的算法,并通过计算每个可能中心的最长回文子串然后取最大值来实现.因此,您应该可以根据自己的需要轻松修改它.

http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/

编辑:第一个链接在仔细检查后看起来有点不稳定,所以这是另一个:

http://zhuhcheng.spaces.live.com/Blog/cns!DE38E96268C49F28!311.entry?wa=wsignin1.0&sa=707413829