Anzahl der Palindrom Teilfolgen der Länge vier

Question

ein String S der Länge n enthält nur Klein englischen Buchstaben Da sind wir Anzahl von Palindrom Subsequenzen Länge kann 4.

Gesamtzahl der Palindrom Teilfolgen berechnen sein berechnet von O(n^2) DP. Aber wie berechnet man die Anzahl solcher Teilfolgen für eine Länge 4 in der Reihenfolge O(n log n) oder O(n)?

Beispiel: "abcdbaadc" hat die Antwort 4. [Indizes (1, 2, 5, 6), (1, 2, 5, 7), (3, 6, 7, 9), (4, 6, 7, 8)]

Jeder Hinweis oder Erklärung wird geschätzt.

Answer 1

Da die Länge 4 ist, können Sie alle möglichen Zeichenfolgen der Länge 4 der Form ABBA aufzählen und für jede Zeichenfolge einen Standardalgorithmus ausführen, um die Anzahl der Untersequenzen dieser bestimmten Zeichenfolge in der angegebenen Zeichenfolge zu finden.

Komplexität: O (n * 26 * 26), n ist die Länge der Zeichenfolge. Im Folgenden finden Sie den Python-Code, um die Anzahl der Untersequenzen einer bestimmten Zeichenfolge in einer anderen Zeichenfolge zu finden.

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]