Longest Common Substring

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

La soluzione di programmazione dinamica richiede un tempo O(n × m) e O(m) di memoria con una sola riga. Estendere da ogni coppia di posizioni iniziali richiede O(n × m × min(n, m)) nel caso peggiore. Un automa dei suffissi raggiunge circa O(n + m) , al costo di un programma molto più lungo.

Q: Come si restituisce direttamente la sottostringa comune più lunga?

Ogni volta che una cella supera best , registra anche la posizione i in s1 in cui termina quel blocco. Alla fine, la sottostringa è composta dalle lettere di s1 che terminano lì, in numero pari a best . Un confronto strettamente maggiore mantiene il primo blocco più lungo trovato in s1 .

MedioProgrammazione dinamica

+10

Ricevi due stringhe, s1 e s2. Una sottostringa è una sequenza ininterrotta di lettere presa da una stringa, come ork da clockwork. Trova la sottostringa più lunga che s1 e s2 hanno in comune e restituiscine la lunghezza. Se nessuna lettera compare in entrambe le stringhe, la risposta è 0.

Funzione

longestCommonSubstring(s1: string, s2: string) → integer

s1string: la prima stringa
s2string: la seconda stringa
Restituisceinteger: la lunghezza del blocco di lettere più lungo presente in entrambe le stringhe

Vincoli

1 ≤ s1.length ≤ 1000
1 ≤ s2.length ≤ 1000
s1 e s2 sono composte da lettere minuscole dell'alfabeto inglese.

Esempi

Input: s1 = "clockwork"s2 = "workshop"
Output: 4
Spiegazione: work conclude clockwork e inizia workshop, quindi è una sottostringa comune di lunghezza 4, e non compare in entrambi alcun blocco più lungo.

Input: s1 = "hammer"s2 = "harmed"
Output: 2
Spiegazione: ha e me compaiono in entrambe le parole, ma non c’è nessuna sequenza di tre lettere. Entrambe le parole contengono h, a, m, e in quest’ordine, ma harmed ha una r tra la a e la m.

Per approfondire

Riesci a verificare se esiste una sottostringa comune di una determinata lunghezza L in circa O(n + m) tempo con un hash rolling, e poi eseguire una ricerca binaria su L?

Suggerimenti

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

0 di 3 aperti

Soluzione

Estendere una corrispondenza da ogni coppia di posizioni iniziali rilegge le stesse lettere. Guarda invece dove un blocco termina: il blocco comune che termina in s1[i] e s2[j] è più lungo di una lettera rispetto a quello che termina nelle due lettere che li precedono, oppure è vuoto se le lettere sono diverse. Una tabella di queste lunghezze fornisce la risposta in O(n × m) tempo.

Estendi da ogni coppia di posizioni iniziali

Corretto, ma non termina sui test più grandi

Intuizione

Ogni sottostringa comune inizia in una certa posizione i di s1 e in una certa posizione j di s2. Per ogni coppia, scorri in avanti finché le lettere corrispondono e conta i passaggi; il conteggio più alto è la risposta.

Il testo ripetitivo rende lunghi gli scorrimenti. Quando entrambe le stringhe sono 1000 copie di a, ogni coppia scorre fino alla fine del suffisso più corto: circa 3.3 × 10^8 confronti tra lettere. Lo scorrimento da (i, j) ripete per intero lo scorrimento da (i+1, j+1), una lettera più avanti.

Algoritmo

Imposta best = 0.
Per ogni i in s1 e ogni j in s2, imposta k = 0.
Mentre sia i+k che j+k sono all'interno delle rispettive stringhe e s1[i+k] == s2[j+k], aggiungi 1 a k.
Conserva il valore più grande di k in best e restituiscilo.

def longestCommonSubstring(s1, s2):
    n, m = len(s1), len(s2)
    best = 0
    for i in range(n):
        for j in range(m):
            # Walk forward while the two strings agree
            k = 0
            while i + k < n and j + k < m and s1[i + k] == s2[j + k]:
                k += 1
            if k > best:
                best = k
    return best

Tabella delle lunghezze dei blocchi che terminano a ogni coppia

Intuizione

Sia run[i][j] la lunghezza del blocco comune più lungo che termina esattamente in s1[i-1] e s2[j-1]; la riga 0 e la colonna 0 contengono 0. Un blocco di questo tipo deve contenere entrambe le lettere. Se sono diverse, non esiste alcun blocco e la cella vale 0. Se corrispondono, il blocco è questa coppia più il blocco che termina una lettera prima in entrambe le stringhe: run[i-1][j-1] + 1. Ogni sottostringa comune termina da qualche parte, quindi la risposta è la cella più grande, ovunque si trovi.

Per hammer e harmed, le h danno 1 e le a estendono il blocco a 2, poi la r interrompe il blocco. La seconda m di hammer incontra la m di harmed dopo una mancata corrispondenza tra m e r, quindi riparte da 1, e le e lo portano a 2. Nessuna cella arriva a 3.

Un confronto per cella: circa un milione per due stringhe di 1000 lettere, qualunque sia il testo.

Algoritmo

Inizializza run con n+1 righe e m+1 colonne, tutte a 0, e imposta best = 0.
Esegui un ciclo su i da 1 a n e, al suo interno, su j da 1 a m, confrontando s1[i-1] con s2[j-1].
In caso di corrispondenza, imposta run[i][j] = run[i-1][j-1] + 1 e aggiorna best.
In caso di mancata corrispondenza, lascia la cella a 0.
Restituisci best.

def longestCommonSubstring(s1, s2):
    n, m = len(s1), len(s2)
    # run[i][j]: length of the longest block that ends at s1[i-1] and at s2[j-1]
    run = [[0] * (m + 1) for _ in range(n + 1)]
    best = 0
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if s1[i - 1] == s2[j - 1]:
                run[i][j] = run[i - 1][j - 1] + 1
                if run[i][j] > best:
                    best = run[i][j]
            # a mismatch leaves run[i][j] at 0
    return best

Una riga, aggiornata da destra a sinistra

Intuizione

Ogni cella legge solo la cella in diagonale in alto a sinistra. Quindi un unico array run di m+1 numeri può contenere la tabella se scorri j da destra a sinistra: quando scrivi run[j], la posizione run[j-1] contiene ancora il valore della lettera precedente di s1, che è la cella diagonale.

Ora una mancata corrispondenza deve scrivere esplicitamente 0, perché la posizione contiene ancora un numero della riga precedente. Il tempo rimane O(n × m) e la memoria scende da circa 10^6 numeri a 1001.

Algoritmo

Crea un array run di m+1 zeri e imposta best = 0.
Per ogni lettera ch di s1, visita j da m fino a 1.
Se ch == s2[j-1], imposta run[j] = run[j-1] + 1 e aggiorna best.
Altrimenti imposta run[j] = 0.
Restituisci best.

def longestCommonSubstring(s1, s2):
    m = len(s2)
    # run[j]: length of the common block that ends at the current letter of s1 and at s2[j-1]
    run = [0] * (m + 1)
    best = 0
    for ch in s1:
        # Right to left, so run[j-1] still holds the value from the previous letter of s1
        for j in range(m, 0, -1):
            if ch == s2[j - 1]:
                run[j] = run[j - 1] + 1
                if run[j] > best:
                    best = run[j]
            else:
                run[j] = 0
    return best

Trappole e casi limite

Restituire l'ultima cella. run[n][m] copre solo i blocchi che terminano con entrambe le ultime lettere. Per abc e abd è 0, mentre ab dà 2.
Copiare il vicino più grande in caso di mancata corrispondenza. Questa è la regola della sottosequenza e permette a un blocco di saltare delle lettere: con hammer e harmed restituisce 4 invece di 2.
Scorrere la singola riga da sinistra a destra. Il valore diagonale viene sovrascritto prima di leggerlo, quindi a confrontato con aa dà 2.
Saltare il ripristino nella singola riga. Una lunghezza della lettera precedente di s1 sopravvive e in seguito estende un blocco che non esiste.
Scorrere la forza bruta senza controllare i limiti. Con zzzz confrontato con zz, legge oltre la fine della stringa più corta.

Domande frequenti3

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

Una sottostringa è una sequenza ininterrotta di lettere; una sottosequenza mantiene l’ordine, ma può lasciare degli spazi. Per hammer e harmed, la sottostringa comune più lunga ha lunghezza 2 e la sottosequenza comune più lunga ha lunghezza 4 (hame). Nelle tabelle, una mancata corrispondenza reimposta a 0 la cella della sottostringa, ma fa sì che la cella della sottosequenza copi il valore del vicino più grande.

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

La soluzione di programmazione dinamica richiede un tempo O(n × m) e O(m) di memoria con una sola riga. Estendere da ogni coppia di posizioni iniziali richiede O(n × m × min(n, m)) nel caso peggiore. Un automa dei suffissi raggiunge circa O(n + m), al costo di un programma molto più lungo.

Come si restituisce direttamente la sottostringa comune più lunga?

Ogni volta che una cella supera best, registra anche la posizione i in s1 in cui termina quel blocco. Alla fine, la sottostringa è composta dalle lettere di s1 che terminano lì, in numero pari a best. Un confronto strettamente maggiore mantiene il primo blocco più lungo trovato in s1.

def longestCommonSubstring(s1, s2):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomenti

s1 = "clockwork"
s2 = "workshop"

Output atteso

Longest Common Substring

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Estendi da ogni coppia di posizioni iniziali

Tabella delle lunghezze dei blocchi che terminano a ogni coppia

Una riga, aggiornata da destra a sinistra

Trappole e casi limite

Domande frequenti3

Problemi simili