给定一个字符串（仅假设英文字符）S为length 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)额外内存的解决方案。我认为没有它是不可能的。

任何好的想法或参考，表示赞赏。