Hledání nejdelšího společného podslova

Hledání nejdelšího společného podslova je úloha z oboru matematické informatiky, jejíž podstatou je pro zadané řetězce najít jejich nejdelší společné podslovo. Na rozdíl od příbuzné úlohy hledání nejdelší společné podposloupnosti je tedy hledána posloupnost znaků souvislá v obou vstupech.

Příklad

Společná podslova tří řetězců „ABABC“, „BABCA“ a „ABCBA“ jsou „A“, „AB“, „ABC“, „B“, „BA“, „BC“ a „C“. Nejdelším podslovem je tedy „ABC“ s délkou tři.

ABABC ||| BABCA ||| ABCBA

Formální zadání

Jsou dána dvě slova, slovo S o délce m a slovo T o délce n. Úlohou je najít nejdelší slovo, které je podslovem obou dvou.

Algoritmy

Základním postupem je hledání pomocí sufixového stromu, což má asymptotickou časovou složitost \Theta(n+m). Metodou dynamického programování je lze nalézat se složitostí \Theta(nm).

Odkazy

Reference

Literatura

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