Longest Common Subsequence

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

La soluzione con tabella ha una complessità temporale di O(n × m) , 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 complessità esponenziale.

MedioProgrammazione dinamica

+10

Ti vengono date 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 adiacenti. 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 minuscole inglesi.

Esempi

Input: text1 = "stone"text2 = "longest"
Output: 3
Spiegazione: o, n, e compaiono in quest’ordine in entrambe le parole, quindi one è comune, lunghezza 3. Le lettere s e t sono alla fine di longest ma all’inizio di stone, quindi usandole si ottiene al massimo st.

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.

Per approfondire

Puoi restituire una delle sottosequenze comuni più lunghe, insieme alla sua lunghezza?

Suggerimenti

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

0 di 3 aperti

Soluzione

L’abbinamento greedy fallisce: associare la c di cab all’ultima c di abc non lascia nulla per a e b; saltarla permette di trovare ab. La risposta per due prefissi dipende dalle risposte per prefissi più brevi, quindi una tabella (n+1) × (m+1) risolve una volta ogni coppia. Ogni riga legge solo la riga precedente, quindi 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:]. Se le loro prime lettere sono uguali, abbinale: una sottosequenza comune più lunga che salta questa coppia può sostituire la sua prima coppia con questa senza diventare più corta. Quindi la risposta è 1 + lcs(i+1, j+1).

Se le lettere sono diverse, non possono essere usate entrambe, perché i loro abbinamenti farebbero incrociare le coppie. Quindi se ne può scartare una: max(lcs(i+1, j), lcs(i, j+1)). Un suffisso vuoto dà 0.

Ogni mancata corrispondenza avvia due chiamate. Due stringhe di 20 lettere senza lettere in comune richiedono già circa 2.8 × 10^11 chiamate, eppure ci sono solo (n+1) × (m+1) coppie diverse (i, j), quindi quasi tutte le chiamate ripetono 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 di prefissi

Intuizione

Sia dp[i][j] la risposta per le prime i lettere di text1 e le prime j lettere di text2, così l’indice 0 indica un prefisso vuoto e la riga 0 e la colonna 0 sono 0. Confronta le ultime lettere dei due prefissi, text1[i-1] e text2[j-1]: se le lettere sono uguali, si accoppiano, dp[i-1][j-1] + 1; se sono diverse, se ne elimina una, max(dp[i-1][j], dp[i][j-1]). È la ricorsione letta dalla fine.

Ogni cella legge le celle sopra, a sinistra e in diagonale in alto a sinistra, quindi riempiendo la tabella riga per riga, da sinistra a destra, le trova sempre già calcolate. Per pear e reap, la riga per pea è [0, 0, 1, 2, 2]; la sua cella per rea è 2 perché a corrisponde ad a, aggiungendo uno alla cella per pe e re.

Due stringhe di 1000 lettere richiedono circa 10^6 passaggi a tempo costante.

Algoritmo

Crea una tabella dp di zeri di dimensione (n+1) × (m+1).
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

Una volta completata una riga, quelle sopra non vengono più lette. Mantieni prev per la riga completata e cur per quella in fase di riempimento, e scambiale dopo ogni riga. La ricorrenza e l’ordine restano gli stessi.

La risposta non dipende da quale stringa viene prima, quindi fai 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.

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

Mescolare gli indici della tabella con gli indici delle stringhe. La cella dp[i][j] confronta text1[i-1] con text2[j-1], perché la riga 0 è 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]. Questo può usare la stessa lettera due volte: aa confrontata con a restituirebbe 2 invece di 1.
Scrivere nella riga da cui si sta ancora leggendo. Con due righe, ogni valore della riga precedente deve provenire da prev e cur[0] deve restare 0.
Memorizzare i risultati della ricorsione in Python su stringhe di 1000 lettere. La profondità delle chiamate raggiunge 2000, oltre il limite predefinito di 1000.

Domande frequenti3

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

La soluzione con tabella ha una complessità temporale di O(n × m), 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 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; una sottostringa è un blocco di lettere adiacenti. Per stone e longest, la sottosequenza comune più lunga è one (3), mentre la sottostringa comune più lunga è on (2). La tabella delle sottostringhe reimposta una cella a 0 in caso di mancata corrispondenza, invece di copiare una cella adiacente.

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

Un diff tra due versioni di un file conserva la sottosequenza comune più lunga delle loro righe e mostra tutte le altre righe come aggiunte o rimosse. Il numero minimo di inserimenti e cancellazioni necessari per trasformare una stringa nell’altra è n + m - 2 × LCS. La distanza di modifica consente anche di sostituire una lettera, quindi richiede una tabella propria.

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

Test #1

Test #2

Test #3

Argomenti

text1 = "stone"
text2 = "longest"

Output atteso

Longest Common Subsequence

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Confronta le prime lettere con la ricorsione

Completa una tabella di prefissi

Mantieni solo due righe

Trappole e casi limite

Domande frequenti3

Problemi simili