algorithm - 计算给定整数序列中的双回文数

Question

对于给定的 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 在这里被视为字母表的单个元素

Answer 1

既然您已经知道找到所有回文的算法(顺便说一句，这非常棒)，您只需执行以下操作。请注意，“双回文”也是回文:
反向(PP) = 反向(P)反向(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²) 在最坏的情况下。我相信这在最坏的情况下应该是最优的(考虑一个全 1 的字符串)。