給定一個字符串長度爲4

Question

的迴文子序列號長僅包含小寫英文字母n的S，我們要計算長度的迴文子序列號爲4的

迴文子序列的總數可由O(n^2) DP計算。但是，如何計算長度爲4的這些子序列的數量爲O(n log n)或O(n)？ （1,2,5,6），（1,2,5,7），（3,6,7,9），（4,6,7,9） 7,8）]

任何暗示或解釋讚賞。

Answer 1

由於長度爲4，因此可以枚舉形式爲ABBA的所有可能的長度爲4的字符串，並且對於每個字符串，運行標準算法以查找給定字符串中該特定字符串的子序列數。

複雜性：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]