string 计算 O(n) 中的回文子串
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3647453/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Counting palindromic substrings in O(n)
提问by IVlad
Given a string (assume only English characters) Sof length n, we can count the number of palindromic substrings with the following algorithm:
给定一个S长度为 的字符串（假设只有英文字符）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
The above code is O(n^2)however.
然而上面的代码是O(n^2)。
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 000on n, however I've never seen the algorithm and can't seem to be able to come up with it.
我对解决这个问题的算法感兴趣O(n)。我肯定知道存在一个，因为我听到很多人说它确实存在，并且问题存在于上限为1 000 000on的本地在线判断站点上n，但是我从未见过该算法并且似乎无法能够想出它。
Update:
更新：
The general idea I have is to compute len[i] = length of the longest palindrome centered at the character 2i + 1and 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.
我的一般想法是len[i] = length of the longest palindrome centered at the character 2i + 1为偶数长度的回文计算一个类似的数组。通过良好的簿记，应该可以O(1)为每个字符计算这个，这将使我们能够一次计算很多回文。然而，我一直在思考如何准确地计算它。
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.
我会接受一个使用O(n)甚至可能O(n log n)额外内存的解决方案。我认为没有它这是不可能的。
Any good ideas or references are appreciated.
任何好的想法或参考都表示赞赏。
采纳答案by Paul Accisano
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.
以下站点显示了一种在 O(n) 时间内计算最长回文子串的算法，它通过在每个可能的中心计算最长回文子串然后取最大值来实现。因此，您应该能够根据自己的目的轻松修改它。
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/
EDIT: 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
http://zhuhcheng.spaces.live.com/Blog/cns!DE38E96268C49F28!311.entry?wa=wsignin1.0&sa=707413829
回答by Aakash Prakash
Consider a string S="aaabb".
考虑一个字符串S="aaabb"。
Append a character '$'at both ends of the string and in between every two consecutive characters to change the string to S="$a$a$a$b$b$"and apply Manacher's algorithmfor this string S.
'$'在字符串的两端和每两个连续字符之间附加一个字符，以将字符串更改为S="$a$a$a$b$b$"并对此字符串应用Manacher 算法S。
New string Sis of length 2n+1 which gives us runtime of O(2n+1) which is same as O(n).
新字符串S的长度为 2n+1，这为我们提供了与 O(n) 相同的 O(2n+1) 运行时间。
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 $
Array Ais the result of Manacher's Algorithm.
数组A是 Manacher 算法的结果。
Now, the summation of A[i]/4for index where '$', else (A[i]+1)/4for every other character from 1<=i<=n is your answer.
现在，总和A[i]/4为指数，其中'$'，否则(A[i]+1)/4从隔日1字<= I <= n为你的答案。
Here, $acts as a center for the even length palidromic substrings and the odd length can be calculated normally. The answer for this case is:
这里，$作为偶数长度回文子串的中心，可以正常计算奇数长度。这个案例的答案是：
0 + 1 + 1 + 2 + 1 + 1 + 0 + 1 + 1 + 1 + 0 = 9 (a,a,aaa,a,b,b,aa,aa,bb).
0 + 1 + 1 + 2 + 1 + 1 + 0 + 1 + 1 + 1 + 0 = 9 (a,a,aaa,a,b,b,aa,aa,bb)。
回答by sth
For "normal" strings it should be rather efficient to look at each character as the potential "center" of a palindrome and then check if the surrounding characters actually build one:
对于“正常”字符串，将每个字符视为回文的潜在“中心”，然后检查周围的字符是否确实构建了一个，应该是相当有效的：
# 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]
For normal strings this should be about O(n), though in the worst case, for example if the string consists of only one character repeated over and over again, it will still take O(n2) time.
对于普通字符串，这应该大约为 O(n)，但在最坏的情况下，例如，如果字符串仅包含一个反复重复的字符，则仍然需要 O(n 2) 时间。
