在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)内解决该问题的算法很感兴趣。我确定存在这样的算法，因为我听到过多个人说它存在，并且该问题存在于一个本地在线评测网站上，n 的上限为1,000,000，但我从未见过该算法，也无法想出来。

更新：

我的大致想法是计算 len[i] = 以字符 2i + 1 为中心的最长回文子串长度，以及偶数长度的回文子串类似的数组。通过良好的记录，应该可以每个字符都在O(1)时间内完成计算，这将使我们能够一次性计算出许多回文子串。然而，我卡在如何确切地计算这个数组上。

我将接受使用O(n)甚至O(n log n)额外内存的解决方案。我认为如果没有额外内存，这是不可能的。

如果有任何好的思路或参考资料，我将不胜感激。

- IVlad

---

你为什么认为这个解决方案是O(n)时间复杂度的？而且，一个需要O(n log n)空间复杂度的O(n)时间复杂度算法确实很奇怪。 - Craig Gidney

@Strilanc - 我认为它是O(n)的，因为有些人提到了这个复杂度，并且唯一能在一百万个字符上运行0.1秒的东西就是O(n)。 - IVlad

相关：编写一个函数，返回给定字符串中最长的回文字符串 - Roger Pate

@IVlad如果您弄清楚了，可以请贴一下代码吗？ - 1110101001

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

- Paul Accisano

---

我把你第一个链接里的 Python 代码翻译成了 C++，看起来是O(n)的。对于一个由单个字符组成的字符串，它可以立即运行，并且它还通过了我尝试的每一个测试。看起来就是这样了，谢谢！ - IVlad

关于最大回文数，如果发现更大的回文数，则会忽略较小的回文数。我想知道是否可以通过修改该算法来计算所有回文数？ - Chan Le

@IVlad，我在Python代码的第70行发现了一个错误。else:语句似乎放错了位置，我不确定它应该放在哪里。 - mbadawi23

@IVlad，您是如何修改算法以计算回文数的数量的？ - 1110101001

@Paul：我认为第一个链接并不靠不住，它们都是描述同一算法——马拉车算法。 - simonzack

Answer 2

对于“普通”的字符串来说，将每个字符视为潜在的回文中心，然后检查周围的字符是否构成回文应该是相当有效的：

# check odd palindromes
for center in range(len(ls)):
   # check how many characters to the left and right of |center|
   # build a palindrome
   maxoffs = min(center, len(ls)-center-1)
   offs = 0
   while offs <= maxoffs and ls[center-offs] == ls[center+offs]:
      offs += 1
   offs -= 1
   print ls[center-offs : center+offs+1]                                    

# check for even palindromes
for center in range(len(ls)-1):
   maxoffs = min(center, len(ls)-center-2)
   offs = 0
   while offs <= maxoffs and ls[center-offs] == ls[center+offs+1]:
      offs += 1
   offs -= 1
   if offs >= 0:
      print ls[center-offs : center+offs+2]

对于普通字符串，时间复杂度应该是O(n)，但在最坏情况下，例如字符串只由一个字符重复多次组成，时间复杂度仍然需要O(n²)。

- sth

---

你确实可以提前停止搜索，这对于随机字符串来说已经足够好了。但我更感兴趣的是总是O(n)的算法。很容易打破这个算法：一个由单个字符组成的字符串。 - IVlad

Answer 3

考虑一个字符串S="aaabb"。

在字符串的两端和每两个相邻字符之间附加一个字符'$'，将字符串更改为S="$a$a$a$b$b$"并对该字符串S应用Manacher's算法。

新的字符串S的长度为2n+1，这使我们的运行时间为O(2n+1)，与O(n)相同。

index :  1 2 3 4 5 6 7 8 9 10 11
A     :  1 3 5 7 5 3 1 3 5  3  1
S     :  $ a $ a $ a $ b $  b  $

数组A是Manacher算法的结果。

现在，对于下标为'$'的字符，求A[i]/4的总和；对于其他下标为1≤i≤n的字符，求(A[i]+1)/4的总和，答案即为所求。

这里，$作为偶数长度回文子串的中心，奇数长度可以正常计算。此案例的答案是：

0 + 1 + 1 + 2 + 1 + 1 + 0 + 1 + 1 + 1 + 0 = 9 (a,a,aaa,a,b,b,aa,aa,bb)。

- Aakash Prakash