Vysvětlete princip fungování algoritmu hledání podřetězce Knuth-Morris-Pratt.
sobes.tech AI
Odpověď od AI
Algoritmus Knuth-Morris-Pratt (KMP) je navržen tak, aby hledal podřetězec v řetězci v lineárním čase, čímž se vyhýbá opakovaným porovnáním znaků.
Hlavní myšlenkou je předem vypočítat pro podřetězec pole prefixových funkcí (nebo "π-pole"), které ukazuje, kolik znaků se shoduje s počátkem podřetězce při neúspěšném porovnání. To umožňuje při neshodě nesestupovat zpět na začátek původního řetězce, ale posunout podřetězec o optimální počet pozic.
Příklad:
- Text: "ABABDABACDABABCABAB"
- Hledaný podřetězec: "ABABCABAB"
Algoritmus nejprve sestaví prefixovou funkci pro podřetězec, poté projde text a porovnává znaky. Při neshodě využívá prefixovou funkci k určení, od kterého znaku podřetězce pokračovat v porovnávání, aniž by začínal od začátku.
Toto zajišťuje složitost O(n + m), kde n je délka textu, m délka podřetězce, což je efektivnější než naivní hledání.