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. Řešení úlohy má rovněž aplikace v počítačové lingvistice a v bioinformatice.

Příklad

Dvě posloupnosti

${\displaystyle X=\langle A,C,B,D,E,G,C,E,D,B,G\rangle }$ a

${\displaystyle Y=\langle B,E,G,C,F,E,U,B,K\rangle }$

mají největší společnou podposloupnost

${\displaystyle \langle B,E,G,C,E,B\rangle }$.

Složitost řešení

Použitím dynamického programování je úloha řešitelná pro ${\displaystyle N}$ vstupních posloupností o délkách ${\displaystyle n_{1},\dots ,n_{N}}$ v čase:

${\displaystyle O\left(N\prod _{i=1}^{N}n_{i}\right).}$

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Longest common subsequence problem na anglické Wikipedii.

Zdroj