Massima sottosequenza comune

Da Wikipedia, l'enciclopedia libera.

Il problema della massima sottosequenza comune (LCS, longest common subsequence) consiste nel trovare la più lunga sottosequenza comune a tutte le stringhe in un insieme di stringhe (solitamente due). Si noti che una sottosequenza non è necessariamente una sottostringa. Questo problema, classico tra i problemi informatici, trova applicazione in bioinformatica oltre ad essere anche la base di "diff" (un software di comparazione di file).