Zobrazení zdroje stránky Hledání nejdelšího společného podslova

{{neověřeno}}
'''Hledání nejdelšího společného podslova''' je úloha z oboru [[matematická informatika|matematické informatiky]], jejíž podstatou je pro zadané [[textový řetězec|řetězce]] najít jejich nejdelší společné [[podslovo]]. Na rozdíl od příbuzné [[hledání nejdelší společné podposloupnosti|ú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 <math>S</math> o délce <math>m</math> a slovo <math>T</math> o délce <math>n</math>. Úlohou je najít nejdelší slovo, které je [[podslovo|podslovem]] obou dvou.

== Algoritmy ==
Základním postupem je hledání pomocí [[sufixový strom|sufixového stromu]], což má [[asymptotická časová složitost|asymptotickou časovou složitost]] <math>\Theta(n+m)</math>. Metodou [[dynamické programování|dynamického programování]] je lze nalézat se složitostí <math>\Theta(nm)</math>.

== Odkazy ==

=== Reference ===
{{překlad|en|Longest common substring problem|884230596}}
<references/>

=== Literatura ===
{{Autoritní data}}

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