Calcolatore LCS

Il problema della sottosequenza comune più lunga chiede la sequenza di caratteri più lunga che compare nello stesso ordine in due stringhe di ingresso, senza richiedere contiguità. È il fondamento di programmazione dinamica degli strumenti di diff per righe, degli aiuti di merge nel controllo di versione, dei rilevatori di plagio che tollerano riordini rumorosi e del confronto di sequenze biologiche quando inserzioni e cancellazioni contano più di una sottostringa esatta. Questo calcolatore di sottosequenza comune più lunga accetta due stringhe, riempie una tabella classica delle lunghezze in tempo lineare rispetto al prodotto delle lunghezze, ricostruisce un LCS valido con backtracking e restituisce sia la lunghezza numerica sia la stringa della sottosequenza. Gli input vuoti sono validi e producono lunghezza zero.

Cos'è (e cosa non è) una sottosequenza comune più lunga

Una sottosequenza di una stringa è qualsiasi stringa ottenuta cancellando zero o più caratteri senza riordinare i superstiti. Una sottosequenza comune di due stringhe è una stringa che è sottosequenza di entrambe. Una sottosequenza comune più lunga, o LCS, è qualsiasi sottosequenza comune la cui lunghezza è massima tra tutte le sottosequenze comuni.

A differenza di una sottostringa comune più lunga, un LCS non deve occupare un blocco contiguo in nessuno degli input: la coppia classica ABCBDAB e BDCABA ammette diverse stringhe LCS di lunghezza quattro, come BCBA e BDAB, a seconda dei pareggi scelti dalla ricostruzione. Gli algoritmi di diff e gli strumenti di allineamento del DNA si basano su questa nozione non contigua perché le modifiche reali inseriscono e cancellano simboli invece di far scorrere solo una finestra fissa.

La lunghezza di un LCS è un punteggio di similarità utile; i caratteri ricostruiti servono quando Lei vuole uno scheletro di allineamento esplicito accanto al punteggio. Non restituisce ogni LCS possibile, script di modifica o percentuali di similarità—sono problemi separati costruiti sulla stessa idea di tabella DP.

Dove la sottosequenza comune è davvero utile

I corsi di informatica e i giudici online hanno bisogno di un oracolo di riferimento che restituisca una lunghezza corretta e una sottosequenza valida per stringhe corte arbitrarie senza che gli studenti incollino soluzioni in un IDE completo. Le funzioni di prodotto vicine al diff—riepiloghi di modifiche, indizi di conflitto di merge, allineamento di righe di log—spesso vogliono la lunghezza LCS come segnale di similarità economico prima di un passaggio più pesante di distanza di edit.

Le demo didattiche di bioinformatica usano stringhe dell'alfabeto DNA giocattolo (A, C, G, T) per mostrare come inserzioni e cancellazioni lasciano comunque un lungo scheletro condiviso. Tenga le stringhe sotto il tetto di lunghezza, fissi la sottosequenza ricostruita nei test se le interessa quale tra più risposte ugualmente lunghe ottiene, e otterrà risultati LCS riproducibili senza montare una libreria numerica propria.