问题描述
给定一个长度 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 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 [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.
编辑：第一个链接看起来有点不稳定，仔细检查，所以这里是另一个：
The first link looks a little shaky upon closer inspection, so here's another one:
这篇关于计数O（n）中的回文子串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！