Celle riempite
Coppie uguali
La più lunga finora

  • In riempimento
  • Letta
  • Risposta

Di più sulla sottosequenza comune più lunga

Sottosequenza comune più lunga (LCS)

Quali lettere hanno in comune due parole, nello stesso ordine? La sottosequenza comune più lunga risponde a questa domanda, e gli strumenti diff, i correttori ortografici e i confronti di DNA si basano su di essa. Scrivi due parole e guarda riempirsi una tabella delle loro lettere, poi ricostruisci la risposta a ritroso partendo dall'angolo. Premi Avvia per guardare la tabella che si riempie, oppure Passo e Indietro per procedere un passo alla volta. Trascina il cursore dei passi per saltare dove vuoi. Scrivi due parole: la prima scorre lungo il lato della tabella, la seconda lungo il bordo superiore. Ogni cella contiene la lunghezza della sottosequenza comune più lunga delle lettere fino alla sua riga e alla sua colonna. Alla fine le lettere vengono rilette a partire dalla cella in basso a destra. Nuovo esempio sceglie un'altra coppia di parole. Con il riquadro selezionato, le frecce vanno avanti e indietro di un passo, la barra spaziatrice avvia e mette in pausa, e Home e Fine saltano all'inizio e alla fine.

Come funziona

  1. Scrivi due parole: la prima scorre lungo il lato della tabella, la seconda lungo il bordo superiore.
  2. Premi Avvia, oppure usa Passo e Indietro per procedere un passo alla volta. Trascina il cursore dei passi per saltare dove vuoi.
  3. Guarda ogni cella confrontare le sue due lettere, poi segui il percorso arancione a ritroso dall'angolo per leggere la risposta.

Come funziona la tabella

Una cella contiene la lunghezza della sottosequenza comune più lunga tra le lettere della prima parola fino alla sua riga e le lettere della seconda parola fino alla sua colonna. La riga e la colonna segnate con – rappresentano una parola vuota, quindi valgono 0. Se le due lettere di una cella sono uguali, la cella vale uno in più della cella in alto a sinistra. Se sono diverse, una delle due lettere non fa parte della risposta, quindi la cella prende il valore più grande tra la cella sopra e la cella a sinistra.

Rileggere le lettere

La cella in basso a destra è la lunghezza della risposta. Per trovare le lettere, parti da lì: dove le due lettere coincidono, quella lettera fa parte della sottosequenza e ti sposti in alto a sinistra; altrimenti ti sposti sulla più grande tra la cella sopra e la cella a sinistra. Le lettere raccolte lungo il percorso, lette al contrario, formano una sottosequenza comune più lunga. Ce ne possono essere altre della stessa lunghezza; la rilettura ne trova una.

Domande frequenti

Qual è la differenza tra una sottosequenza e una sottostringa?

Una sottostringa è una serie di lettere una accanto all'altra, come ACE in RACER. Una sottosequenza mantiene l'ordine ma può saltare lettere, quindi ACE è anche una sottosequenza di ABCDE. La sottostringa comune più lunga è un problema diverso, con una tabella simile.

Quanto è veloce l'algoritmo LCS?

Per parole di lunghezza m e n la tabella ha m·n celle, ognuna riempita in un passo, quindi il lavoro è O(m·n). Per due testi di 10.000 righe sono 100 milioni di celle, ed è per questo che gli strumenti diff usano metodi più furbi basati sulla stessa idea.

La sottosequenza comune più lunga è unica?

No. ABCBDAB e BDCABA hanno tre diverse sottosequenze comuni di lunghezza 4: BCBA, BCAB e BDAB. La tabella dà la lunghezza; la rilettura ne sceglie una.

La LCS dice quanto sono simili due parole?

In parte. Due parole di lunghezza m e n con una sottosequenza comune più lunga di lunghezza k possono essere trasformate l'una nell'altra cancellando m − k lettere e inserendone n − k. La distanza di edit, che permette anche di sostituire una lettera, è spesso una misura migliore.

Viene inviato qualcosa da qualche parte?

No. Tutto viene calcolato nel tuo browser, e le tue ultime impostazioni restano nella memoria locale di questo browser.

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Vai all'editor