1

对于给定的 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

Manacher 对于乞讨是显而易见的，但我不确定下一步该做什么。任何想法表示赞赏。我猜复杂度应该低于 n^2。

编辑： int 在这里被视为字母表的单个元素

4

2 回答 2

0

我将从 2 个系列开始：

  • “成长”序列的集合
  • “收缩”序列的集合

该算法的工作原理如下：

  • 最初两个集合都是空的
  • 一个一个地处理向量的值，假设我们现在正在查看值 V
  • 循环遍历所有“增长”序列
    • 如果增长序列的最后一个值等于 V，则将增长序列复制到收缩序列集合中，从新收缩序列的末尾移除 V
    • 如果增长序列的最后一个值等于 V，则将增长序列复制到收缩序列的集合中，从收缩序列中删除最后 2 个元素（V 和最后一个）
  • 循环遍历所有“缩小”序列
    • 如果收缩序列的最后一个值等于 V，则将其从收缩序列中删除。如果一个收缩序列变成空的，我们就找到了一个回文序列。
    • 如果收缩序列的最后一个值不等于V，则删除这个收缩序列
  • 最后制作一个新的仅由 V 组成的生长序列

事实上，增长的序列是可能曾经成为回文的序列，而收缩的序列是“部分”回文。

于 2010-06-09T20:30:32.347 回答
0

由于您已经知道查找所有回文的算法（顺便说一句，这非常棒），您需要做的就是以下内容。请注意，“双回文”也是回文：
reverse(PP) = reverse(P)reverse(P) = PP。

所以在(a,b)你找到的所有回文中（(a,b)我的意思是从一个位置a到另一个位置的回文b），你需要找到(i,j,k)这样的(i,j)，(j,k)和(i,k)都是回文，并且j-i=k-j。等效地，对于您找到的每个回文(i,j)，您只需要设置k = 2j-i，并检查两者(k,j)和是否(i,k)都是回文。

如果第一步总共返回 M 个回文，这需要 O(M) 时间（假设您存储它们以便检查是否存在回文是 O(1)），因此在最坏的情况下为O(n 2 )。我相信这在最坏的情况下应该是最佳的（考虑一串全 1）。

于 2010-07-17T04:45:16.840 回答