计算给定 int 序列中的双回文数
对于给定的 int 序列，检查双回文的数量，其中双回文是指两个相同回文的序列，它们之间没有中断。例如：
在 1 0 1 1 0 1 中，我们有 1 0 1 作为回文数，它连续出现了 2 次，
在 1 0 1 5 1 0 1 中，我们有 1 0 1 但它是分开的
（除了这些序列）
问题示例测试数据是：
3
12 0 1 1 0 0 1 1 0 0 1 1 0
12 1 0 1 0 1 0 1 0 1 0 1 0
6 3 3 3 3 3 3
含答案
8 0 9
马纳赫显然是在乞讨，但我不知道下一步该做什么。任何想法表示赞赏。我猜复杂度应该低于 n^2。
编辑： int 在这里被视为字母表的单个元素
For a given int sequence check number of double palindromes, where by double palindrome we mean sequence of two same palindromes without break between them. So for example:
in 1 0 1 1 0 1 we have 1 0 1 as a palindrome which appears 2 times without a break,
in 1 0 1 5 1 0 1 we have 1 0 1 but it's separated
(apart from the other palindromes in these sequences)
Problem example test data is:
3
12 0 1 1 0 0 1 1 0 0 1 1 0
12 1 0 1 0 1 0 1 0 1 0 1 0
6 3 3 3 3 3 3
with answers
8 0 9
Manacher is obvious for the begging, but I'm not sure what to do next. Any ideas appreciated. Complexity should be below n^2 I guess.
EDIT: int is here treated as single element of alphabet
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
由于您已经知道查找所有回文的算法（顺便说一句，该算法非常棒），因此您需要做的就是以下操作。请注意，“双回文”也是回文：
反向(PP) = 反向(P) 反向(P) = PP。
因此，在所有回文
(a,b)中，您会发现（其中(a,b)是指从位置a到位置 < code>b)，您需要找到(i,j,k)使得(i,j),(j,k)和(i,k)都是回文，并且ji=kj。同样，对于找到的每个回文(i,j)，只需设置k = 2j-i，并检查是否都(k,j)和(i,k)是回文。如果第一步总共返回 M 个回文，则需要 O(M) 时间（假设您存储它们以便检查回文是否存在为 O(1)），因此 O(n2)最坏的情况。我相信这在最坏的情况下应该是最佳的（考虑全 1 的字符串）。
Since you already know an algorithm for finding all palindromes (which BTW is pretty awesome), all you need to do is the following. Note that a "double palindrome" is also a palindrome:
reverse(PP) = reverse(P)reverse(P) = PP.
So among all palindromes
(a,b)you find (where by(a,b)I mean a palindrome from positionato positionb), you need to find(i,j,k)such that(i,j),(j,k), and(i,k)are all palindromes, andj-i=k-j. Equivalently, for each palindrome(i,j)you find, you just need to setk = 2j-i, and check whether both(k,j)and(i,k)are palindromes.If the first step returns M palindromes in all, this takes O(M) time (assuming you stored them such that checking whether a palindrome exists is O(1)), so O(n2) in the worst case. I believe this should be optimal in the worst case (consider a string of all 1s).
我将从 2 个集合开始：
集合算法的工作原理如下：
实际上，增长序列是可能一次成为回文的序列，而收缩序列是“部分”的一个回文。
I would start with 2 collections:
The algorithm works like this:
In fact the growing sequences are sequences that might become a palindrome once, while the shrinking sequences are 'partially' a palindrome.