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

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání

Hledání nejdelšího společného podslova je úloha z oboru matematické informatiky, jejíž podstatou je pro zadané řetězcea 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[editovat | editovat zdroj]

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í[editovat | editovat zdroj]

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

Algoritmy[editovat | editovat zdroj]

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

Odkazy[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

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

Literatura[editovat | editovat zdroj]