Selgitage Knuth-Morris-Pratt alampärase otsingu algoritmi tööpõhimõtet.
sobes.tech AI
Vastus AI-lt
Knuth-Morris-Pratt (KMP) algoritm on loodud selleks, et otsida alamstringi tekstis lineaarse ajaga, vältides korduvaid märkide võrdlusi.
Põhitees on eelnevalt arvutada alamstringi jaoks prefiksfunktsioonide massiiv (või "π-massiiv"), mis näitab, mitu märki kattuvad alamstringi algusega ebaõnnestunud võrdluse ajal. See võimaldab, kui kattumine puudub, mitte naasta algusesse, vaid liigutada alamstringi optimaalsele positsioonile.
Näide:
- Tekst: "ABABDABACDABABCABAB"
- Otsitav alamstring: "ABABCABAB"
Algoritm koostab esmalt prefiksfunktsiooni alamstringile, seejärel läbib teksti, võrreldes märke. Kui kattumine puudub, kasutab ta prefiksfunktsiooni, et määrata, millisest märgist alustada võrdlust, ilma algusest uuesti alustamata.
See tagab O(n + m) keerukuse, kus n on teksti pikkus, m on alamstringi pikkus, ning on tõhusam kui naiivne otsing.