Hledání nejdelší společné podposloupnosti

Hledání nejdelší společné podposloupnosti je úloha z oboru matematické informatiky, jejíž podstatou je pro zadané posloupnosti nalézt nejdelší posloupnost, která je podposloupností obou dvou. Od příbuzného problému hledání nejdelšího společného podslova se liší tím, že podslovem se rozumí nepřerušený, souvislý sled v daných posloupnostech, zatímco podposloupnost může být s „přeskakováním prvků“.

Podúloha hledání nejdelší společné podposloupnosti se objevuje při řadě jiných problémů. Je základem jedné z definice editační vzdálenosti a také srovnávacích programů typu diff, které jsou dále rozvíjeny verzovacími systémy, jako je například Git. +more Řešení úlohy má rovněž aplikace v počítačové lingvistice a v bioinformatice.

Příklad

Dvě posloupnosti : X = \langle A,C,B,D,E,G,C,E,D,B,G \rangle a : Y = \langle B,E,G,C,F,E,U,B,K \rangle mají největší společnou podposloupnost : \langle B,E,G,C,E,B \rangle .

Složitost řešení

Použitím dynamického programování je úloha řešitelná pro N vstupních posloupností o délkách n_1,\dots,n_N v čase: :O\left(N \prod_{i=1}^{N} n_i\right).

Odkazy

Reference

Kategorie:Kombinatorika Kategorie:Úlohy na řetězcích