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

Question

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

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 000 on n，但是我从未见过该算法，而且似乎无法想出它。

更新:

我的一般想法是计算 len[i] = 以字符 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