长度为 5 的回文数

Question

给定一个二进制字符串 S，找到长度为 5 的回文子序列的数量。长度为 5 的回文子序列是数组 a < b < c < d < e 的 5 个递增索引的列表，使得 S[a 的串联]S[b]S[c]S[d]S[e] 形成回文。如果两个回文子序列的索引列表不同，则认为它们不同。

我的想法：

我想出了如下的递归：

palin(s) = palin(s[1:]) +palin(s[:-1]) -palin(s[1:-1])

当 s[0] !=s[-1] 时，就是上面的情况。我们可以类似地处理其他情况。但这并不能只处理长度为 5 的回文。它将返回回文子序列的总数。我不确定这是否可以扩展以找到解决方案。有什么想法吗？

Answer 1

考虑下一个（线性复杂度）方法：

长度为 5 的回文由任何中心数字组成，0..0, 0..1, 1..0, 1..1左侧有一对数字，0..0, 1..0, 0..1, 1..1左侧有一对对称数字。

因此，您可以从左到右遍历字符串，存储每个索引左侧每种可能对的数量，反方向执行相同操作。那么以索引为中心的回文数i是

P[i] = (Num of 00 left to i) * (Num of 00 right to i) + 
       (Num of 01 left to i) * (Num of 10 right to i) +    
       (Num of 10 left to i) * (Num of 01 right to i) + 
       (Num of 11 left to i) * (Num of 11 right to i) 

回文总数是P[i]超出i=2..Len-2范围的总和

如何获得 i 剩下的对数？只需计算 0 和 1，然后使用以下计数：

if S[i-1] == 0:
   (Num of 01 left to i) = (Num of 01 left to i-1) 
   (Num of 11 left to i) = (Num of 11 left to i-1) 
   (Num of 10 left to i) = (Num of 10 left to i-1) + (Count_1) 
   (Num of 00 left to i) = (Num of 00 left to i-1) + (Count_0)
   Count_0 += 1  
else:              #  1 forms new 0-1 pairs for all 0's at the left
                   #  and  new 1-1 pairs for all 1's at the left           
   (Num of 01 left to i) = (Num of 01 left to i-1) + (Count_0)
   (Num of 11 left to i) = (Num of 11 left to i-1) + (Count_1)
   (Num of 00 left to i) = (Num of 00 left to i-1)
   (Num of 10 left to i) = (Num of 10 left to i-1)
   Count_1 += 1 

要检查的 Python 代码（哑函数检查所有可能的组合以批准结果）

import itertools
def dumb(s):
    n = len(s)
    res = 0
    # produces all indices combinations
    for comb in itertools.combinations(range(n), 5):
        if s[comb[0]]==s[comb[4]] and s[comb[1]]==s[comb[3]]:
            res += 1
    return res

def countPal5(s):
    n = len(s)
    pairs = [[0, 0, 0, 0] for _ in range(n)]
    cnts = [0,0]
    for i in range(1, n-2):
        if s[i-1] == "0":
            if i >= 2:
                pairs[i-1][0]=pairs[i-2][0]+cnts[0]
                pairs[i-1][1]=pairs[i-2][1]
                pairs[i-1][2]=pairs[i-2][2]+cnts[1]
                pairs[i-1][3]=pairs[i-2][3]
            cnts[0] += 1
        else:
            if i >= 2:
                pairs[i-1][0]=pairs[i-2][0]
                pairs[i-1][1]=pairs[i-2][1]+cnts[0]
                pairs[i-1][2]=pairs[i-2][2]
                pairs[i-1][3]=pairs[i-2][3]+cnts[1]
            cnts[1] += 1
    #print(pairs)

    cnts = [0,0]
    res = 0
    for i in range(n-2, 1, -1):
        if s[i+1] == "0":
            if i < n-2:
                pairs[i+1][0]=pairs[i+2][0]+cnts[0]
                pairs[i+1][1]=pairs[i+2][1]
                pairs[i+1][2]=pairs[i+2][2]+cnts[1]
                pairs[i+1][3]=pairs[i+2][3]
            cnts[0] += 1
        else:
            if i < n-2:
                pairs[i+1][0]=pairs[i+2][0]
                pairs[i+1][1]=pairs[i+2][1]+cnts[0]
                pairs[i+1][2]=pairs[i+2][2]
                pairs[i+1][3]=pairs[i+2][3]+cnts[1]
            cnts[1] += 1
        res += pairs[i+1][0]*pairs[i-1][0] + pairs[i+1][1]*pairs[i-1][2] + pairs[i+1][2]*pairs[i-1][1] + pairs[i+1][3]*pairs[i-1][3]
    return res



    print(pairs)

print(countPal5("0110101001"))
print(dumb("0110101001"))

>>68
>>68

   

Answer 2

1. 假设您有一个函数count(pattern, l,r)返回 substring 中模式的出现次数string[l:r]。
2. 对于每个索引，将其视为回文子串的中心。左边有 2 个元素，右边有 2 个元素。现在，这 2 个元素只能有 4 个不同的值（从 0 到 3）。
3. 对于索引i，以元素为中心的回文字符串的数量i-th为sum(count(binary(x), 0,i) + count(binary(x).reverse, i, len(string)))，其中x位于范围内[0,3]并binary(x)返回整数 的二进制字符串表示形式x。

这种方法需要O(n * 4 * complexity of count function)时间。

如何构建count函数？通过预处理/记忆，您可以轻松及时地获取模式出现的次数O(1)。提示：只有 4 个模式需要跟踪，每个模式只需要 2 次计数。简单的计数和操作就可以完成工作。