计算 O(n) 中的回文子串 [英] Counting palindromic substrings in O(n)

问题描述

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

Given a string (assume only English characters) S of length n, we can count the number of palindromic substrings with the following algorithm:

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) 中解决这个问题的算法感兴趣.我确信存在一个，因为我听到很多人说它确实存在，并且问题存在于本地在线法官网站上，n<上的上限为 1 000 000/code>，但我从未见过算法，似乎无法想出它.

I am interested in an algorithm that solves this problem in O(n). I know for sure that one exists as I've heard multiple people say that it does, and the problem exists on a local online judge site with an upper bound of 1 000 000 on n, however I've never seen the algorithm and can't seem to be able to come up with it.

更新:

我的一般想法是计算 len[i] = 以字符 2i + 1 为中心的最长回文的长度 和用于偶数长度回文的类似数组.有了好的簿记，应该可以在 O(1) 中为每个字符计算这个，这将允许我们一次计算很多回文.然而，我一直在思考如何准确地计算它.

The general idea I have is to compute len[i] = length of the longest palindrome centered at the character 2i + 1 and a similar array for even-length palindromes. With good bookkeeping, it should be possible to compute this in O(1) for each character, which will allow us to count a lot of palindromes all at once. I'm stuck on how exactly to compute this however.

我会接受使用 O(n) 甚至 O(n log n) 额外内存的解决方案.我认为没有它这是不可能的.

I will accept a solution that uses O(n) and maybe even O(n log n) extra memory. I think this is impossible without it.

感谢任何好的想法或参考.

Any good ideas or references are appreciated.

推荐答案

以下站点展示了一种在 O(n) 时间内计算最长回文子串的算法，并通过计算每个可能中心的最长回文子串和然后取最大值.因此，您应该能够根据自己的目的轻松修改它.

The following site shows an algorithm for computing the longest palindromic substring in O(n) time, and does so by computing the longest palindromic substring at every possible center and then taking the maximum. So, you should be able to easily modify it for your purposes.

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

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

The first link looks a little shaky upon closer inspection, so here's another one:

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

这篇关于计算 O(n) 中的回文子串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！