Longest Common Subsequence

Q: Qual è la complessità temporale della sottosequenza comune più lunga?

La soluzione con tabella richiede un tempo O(n × m) , dove n e m sono le due lunghezze: riempie una cella per ogni coppia di prefissi. Richiede O(n × m) di memoria per la tabella completa, oppure O(min(n, m)) con due righe. La ricorsione semplice senza tabella ha una complessità esponenziale.

Q: Come si stampa la sottosequenza comune più lunga?

Riempi l'intera tabella, poi torna indietro da dp[n][m] . Quando le due lettere nella cella corrente corrispondono, quella lettera fa parte della risposta: annotala e spostati in diagonale verso l'alto e a sinistra. Altrimenti, spostati nella cella vicina sopra o a sinistra che contiene il valore maggiore. Alla fine, inverti l'ordine delle lettere annotate. La versione con due righe non può farlo, perché ha eliminato le righe precedenti.

MedioProgrammazione dinamica

+10

Ricevi due stringhe, text1 e text2. Una sottosequenza di una stringa conserva alcune delle sue lettere nell’ordine originale e scarta le altre; le lettere conservate non devono essere necessariamente vicine. Restituisci la lunghezza della stringa più lunga che è una sottosequenza di entrambe, oppure 0 se le due stringhe non hanno lettere in comune.

Funzione

longestCommonSubsequence(text1: string, text2: string) → integer

text1string: la prima stringa
text2string: la seconda stringa
Restituisceinteger: la lunghezza della sottosequenza comune più lunga

Vincoli

1 ≤ text1.length ≤ 1000
1 ≤ text2.length ≤ 1000
Entrambe le stringhe contengono solo lettere inglesi minuscole.

Esempi

Input: text1 = "stone"text2 = "longest"
Output: 3
Spiegazione: o, n, e compaiono in quest’ordine in entrambe le parole, quindi one è una sottosequenza comune di lunghezza 3. In longest le lettere s e t vengono per ultime, mentre in stone vengono per prime, quindi una sottosequenza comune che le usa può essere solo st, che è più corta.

Input: text1 = "pear"text2 = "reap"
Output: 2
Spiegazione: ea compare in entrambe le parole. La p e la r si trovano ai lati opposti di ea nelle due parole, quindi nessuna delle due può unirsi a esso, e la risposta è 2.

+19 test nascosti all’invio

Per approfondire

Puoi restituire una delle sottosequenze comuni più lunghe, non solo la sua lunghezza?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

L'abbinamento greedy delle lettere non funziona. Una lettera può corrispondere a molte posizioni nell'altra stringa e la prima corrispondenza può impedire quelle migliori: abbinare la c di cab alla c alla fine di abc non lascia nulla per a e b, mentre saltarla permette di trovare ab. L'idea che risolve il problema è che la risposta per due prefissi dipende solo dalle risposte per prefissi leggermente più brevi. Una tabella di (n+1) × (m+1) numeri risolve ogni coppia una sola volta e, poiché ogni riga legge solo quella sopra, bastano due righe.

Confronta le prime lettere con la ricorsione

Corretto, ma non termina sui test più grandi

Intuizione

Sia lcs(i, j) la risposta per i suffissi text1[i:] e text2[j:]. Guarda le loro prime lettere. Se sono uguali, abbinale: una sottosequenza comune più lunga che non usa questa coppia può sostituire la sua prima coppia con questa senza accorciarsi. Quindi la risposta è 1 + lcs(i+1, j+1).

Se le lettere sono diverse, non possono essere usate entrambe, perché ciascuna potrebbe essere abbinata solo a una lettera successiva dell’altra stringa e le coppie si incrocerebbero. Quindi si può scartare una delle due: la risposta è max(lcs(i+1, j), lcs(i, j+1)). Quando uno dei due suffissi è vuoto, non c’è nulla in comune e la risposta è 0.

È lento perché ogni mancata corrispondenza avvia due chiamate. Se le stringhe non hanno lettere in comune, ogni chiamata trova una mancata corrispondenza finché una delle stringhe non termina, e il numero di chiamate cresce come il numero di modi per intercalare le due stringhe. Per due stringhe di 20 lettere sono circa 2.8 × 10^11 chiamate; i test più grandi hanno 1000 lettere ciascuno. Eppure ci sono solo (n+1) × (m+1) coppie (i, j) diverse, quindi quasi ogni chiamata ripete una chiamata precedente.

Algoritmo

Scrivi lcs(i, j) per i suffissi che iniziano in i e j.
Se i o j supera la fine della rispettiva stringa, restituisci 0.
Se text1[i] == text2[j], restituisci 1 + lcs(i+1, j+1).
Altrimenti restituisci max(lcs(i+1, j), lcs(i, j+1)).
La risposta è lcs(0, 0).

def longestCommonSubsequence(text1, text2):
    def lcs(i, j):
        # The longest common subsequence of text1[i:] and text2[j:]
        if i == len(text1) or j == len(text2):
            return 0
        if text1[i] == text2[j]:
            return 1 + lcs(i + 1, j + 1)
        return max(lcs(i + 1, j), lcs(i, j + 1))

    return lcs(0, 0)

Completa una tabella dei prefissi

Intuizione

Stato. Sia dp[i][j] la sottosequenza comune più lunga delle prime i lettere di text1 e delle prime j lettere di text2. Lavorare con i prefissi permette di usare l’indice 0 per indicare una stringa vuota.

Ricorrenza. Confronta le ultime lettere dei due prefissi, text1[i-1] e text2[j-1]. Se sono uguali, abbinale: dp[i][j] = dp[i-1][j-1] + 1. Altrimenti, scartane una: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). È lo stesso ragionamento della ricorsione, letto a partire dalla fine. Caso base: la riga 0 e la colonna 0 contengono 0, perché un prefisso vuoto non ha nulla in comune con alcunché. Ordine: ogni cella legge quella sopra, quella alla sua sinistra e quella in diagonale in alto a sinistra, quindi riempiendo la tabella riga per riga, da sinistra a destra, queste celle sono sempre già pronte. La risposta è dp[n][m].

Per pear e reap, la riga per pea è [0, 0, 1, 2, 2]. La sua cella per rea è 2 perché a corrisponde ad a, quindi vale uno in più della cella per pe e re, che è 1. L’ultima cella, pear rispetto a reap, confronta r con p, che sono diverse, e prende il maggiore dei due valori adiacenti, 2.

La tabella ha (n+1) × (m+1) celle e ciascuna richiede un lavoro costante: circa 10^6 passaggi per due stringhe di 1000 lettere. Una versione memoizzata della ricorsione riempie le stesse celle, ma effettua chiamate ricorsive fino a una profondità di n + m, superando così la dimensione predefinita dello stack delle chiamate in linguaggi come Python.

Algoritmo

Crea una tabella dp di (n+1) × (m+1) zeri.
Per i da 1 a n e j da 1 a m, confronta text1[i-1] con text2[j-1].
In caso di corrispondenza, imposta dp[i][j] = dp[i-1][j-1] + 1.
Altrimenti, imposta dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
Restituisci dp[n][m].

def longestCommonSubsequence(text1, text2):
    n, m = len(text1), len(text2)
    # dp[i][j]: the longest common subsequence of text1[:i] and text2[:j].
    # Row 0 and column 0 stay 0: an empty prefix has nothing in common.
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]

Mantieni solo due righe

Intuizione

La riga i della tabella legge solo la riga i-1 e le proprie celle precedenti. Una volta completata una riga, tutte le righe sopra di essa non vengono più lette. Quindi tieni due array, prev per la riga completata e cur per la riga in compilazione, e scambiali dopo ogni riga. La ricorrenza e l’ordine restano esattamente gli stessi.

Una sottosequenza comune di due stringhe non dipende da quale stringa viene prima, quindi puoi scambiarle e far scorrere le righe lungo quella più corta. Ogni riga contiene quindi min(n, m) + 1 numeri: 1001 invece di un milione di celle per gli input più grandi, con gli stessi 10^6 passaggi di lavoro.

La prima voce di ogni riga rappresenta un prefisso vuoto della stringa più corta, quindi deve rimanere 0. La risposta è l’ultima voce dell’ultima riga completata.

Algoritmo

Se text2 è più lungo di text1, scambiali.
Crea prev e cur, ciascuno con m + 1 zeri, dove m è la lunghezza minore.
Per ogni lettera di text1, riempi cur[1..m] con la stessa regola della tabella, leggendo prev per la riga sopra.
Scambia prev e cur.
Restituisci prev[m].

def longestCommonSubsequence(text1, text2):
    if len(text2) > len(text1):
        text1, text2 = text2, text1  # keep the rows as short as the shorter string
    m = len(text2)
    # prev[j]: the answer for the previous prefix of text1 and text2[:j]
    prev = [0] * (m + 1)
    for ch in text1:
        cur = [0] * (m + 1)
        for j in range(1, m + 1):
            if ch == text2[j - 1]:
                cur[j] = prev[j - 1] + 1
            else:
                cur[j] = max(prev[j], cur[j - 1])
        prev = cur
    return prev[m]

Trappole e casi limite

La ricorrenza è breve e la maggior parte dei bug consiste in uno scarto di uno o nell’aggiungere una corrispondenza nel posto sbagliato.

Confondere gli indici della tabella con quelli della stringa. La cella dp[i][j] confronta text1[i-1] con text2[j-1], perché la riga 0 rappresenta il prefisso vuoto.
In caso di corrispondenza, aggiungere uno a max(dp[i-1][j], dp[i][j-1]) invece che a dp[i-1][j-1]. In questo modo si può usare due volte la stessa lettera: con aa e a si otterrebbe 2 invece di 1.
Cercare corrispondenze in modo greedy usando due puntatori. cab e abc abbinano le due lettere c e restituiscono 1, mentre ab dà 2.
Scrivere nella riga da cui si stanno ancora leggendo i valori. Con due righe, ogni valore della riga precedente deve provenire da prev e cur[0] deve rimanere 0.
Risolvere per errore il problema della sottostringa comune più lunga. Una sottosequenza può saltare delle lettere; una sottostringa no.
Usare la memoizzazione con la ricorsione su stringhe di 1000 lettere. La profondità delle chiamate raggiunge 2000, superando il limite predefinito di Python, pari a 1000.

Domande frequenti4

Qual è la complessità temporale della sottosequenza comune più lunga?

La soluzione con tabella richiede un tempo O(n × m), dove n e m sono le due lunghezze: riempie una cella per ogni coppia di prefissi. Richiede O(n × m) di memoria per la tabella completa, oppure O(min(n, m)) con due righe. La ricorsione semplice senza tabella ha una complessità esponenziale.

Qual è la differenza tra la sottosequenza comune più lunga e la sottostringa comune più lunga?

Una sottosequenza può saltare delle lettere, purché l’ordine venga mantenuto, mentre una sottostringa è un blocco di lettere adiacenti. Per stone e longest, la sottosequenza comune più lunga è one (3), ma la sottostringa comune più lunga è on (2). La versione con le sottostringhe usa una tabella simile, ma in caso di mancata corrispondenza reimposta la cella a 0 invece di copiare una cella vicina.

Come si stampa la sottosequenza comune più lunga?

Riempi l'intera tabella, poi torna indietro da dp[n][m]. Quando le due lettere nella cella corrente corrispondono, quella lettera fa parte della risposta: annotala e spostati in diagonale verso l'alto e a sinistra. Altrimenti, spostati nella cella vicina sopra o a sinistra che contiene il valore maggiore. Alla fine, inverti l'ordine delle lettere annotate. La versione con due righe non può farlo, perché ha eliminato le righe precedenti.

In che modo LCS è correlata agli strumenti diff e alla distanza di modifica?

Una differenza tra due versioni di un file individua la sottosequenza comune più lunga delle loro righe; ogni riga al di fuori di essa viene mostrata come aggiunta o rimossa. Allo stesso modo, il numero minimo di inserimenti e cancellazioni per trasformare una stringa nell’altra è n + m - 2 × LCS. La distanza di modifica consente anche di sostituire una lettera, quindi usa una propria tabella con una terza scelta per cella.

Python

def longestCommonSubsequence(text1, text2):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

text1 = "stone"
text2 = "longest"

Atteso

Longest Common Subsequence

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Confronta le prime lettere con la ricorsione

Completa una tabella dei prefissi

Mantieni solo due righe

Trappole e casi limite

Domande frequenti4

Problemi simili