Email Gateway (Dec 12 2023 at 14:03): Email Gateway (Dec 12 2023 at 14:03):From: Tobias Nipkow <nipkow@in.tum.de>
Knuth–Morris–Pratt String Search
Lawrence C. Paulson
The naive algorithm to search for a pattern within a string compares
corresponding characters from left to right, and in case of a mismatch, shifts
one position along and starts again. The worst-case time is . Knuth–Morris–Pratt
exploits the knowledge gained from the partial match, never re-comparing
characters that matched and thereby achieving linear time. At the first
mismatched character, it shifts as far to the right as safely possible. To do
so, it consults a precomputed table, based on the pattern. The KMP algorithm is
proved correct.
https://www.isa-afp.org/entries/KnuthMorrisPratt.html
Enjoy!
Last updated: Apr 29 2024 at 04:18 UTC