计数回文子在O（N） [英] Counting palindromic substrings in O(n)

问题描述

给定一个字符串（假设只有英文字符）取值长度 N ，我们可以指望的回文数子与下面的算法：

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

以上code是为O（n ^ 2）但是。

我感兴趣的一个算法，解决了这个问题，在 O（N）。我知道肯定存在，因为我已经听到多次人说，这样做，而且存在于本地的在线法官站点上限为 1 000 000 问题在 N ，但是我从来没有见过的算法似乎没有能够拿出吧。

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个[我] =长度最长的回文集中在人物的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.

什么好的意见或引用美联社preciated。

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.

<一个href="http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/">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:

<一个href="http://zhuhcheng.spaces.live.com/Blog/cns!DE38E96268C49F28!311.entry?wa=wsignin1.0&sa=707413829">http://zhuhcheng.spaces.live.com/Blog/cns!DE38E96268C49F28!311.entry?wa=wsignin1.0&sa=707413829

这篇关于计数回文子在O（N）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！