1

S给定一个长度只包含小写英文字母的字符串n，我们要计算长度为 4 的回文子序列的数量。

回文子序列的总数可以通过 计算O(n^2) DP。但是如何按顺序计算长度为 4 的此类子序列的数量O(n log n)？O(n)

示例：“abcdbaadc”的答案为 4。 [索引 (1, 2, 5, 6), (1, 2, 5, 7), (3, 6, 7, 9), (4, 6, 7, 8) ]

任何提示或解释表示赞赏。

4

1 回答 1

2

由于长度为 4，因此您可以枚举所有可能的长度为 4 的 ABBA 形式的字符串，并且对于每个字符串，运行标准算法来查找给定字符串中该特定字符串的子序列数。

复杂度：O(n*26*26)，n是字符串的长度。下面是用于在另一个字符串中查找特定字符串的子序列数的 python 代码。

def num_subsequences(seq, sub):
m, n = len(seq)+1, len(sub)+1
table = [[0]*n for i in xrange(m)]
def count(iseq, isub):
    if not isub:
        return 1
    elif not iseq:
        return 0
    return (table[iseq-1][isub] +
           (table[iseq-1][isub-1] if seq[m-iseq-1] == sub[n-isub-1] else 0))
for row in xrange(m):
    for col in xrange(n):
        table[row][col] = count(row, col)
return table[m-1][n-1]
于 2016-07-24T13:58:10.743 回答