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

úloha z programování

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říkladEditovat

Dvě posloupnosti

  a
 

mají největší společnou podposloupnost

 .

Složitost řešeníEditovat

Použitím dynamického programování je úloha řešitelná pro   vstupních posloupností o délkách   v čase:

 

OdkazyEditovat

ReferenceEditovat

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