EXAMPLE HERE IS A SIMPLE EXAMPLEBy clicking on the linked character you can see how the Knuth-Pratt-Morris (KPM) algorithm searches in this example.
EXAMPLE HERE IS A SIMPLE EXAMPLENote that the
E in the text matches
the corresponding character in the pattern. So instead of sliding the
pattern down we'll check whether the next character matches.
EXAMPLE HERE IS A SIMPLE EXAMPLENote that since
R does not match
X we can slide the pattern down.
The ``naive'' string searching algorithm would move the pattern down by
one. But the KPM algorithm exploits the fact that the ER discovered in the text does not occur as an initial
substring of the pattern and hence will slide the pattern down by 2.
EXAMPLE
HERE IS A SIMPLE EXAMPLE
EXAMPLE
HERE IS A SIMPLE EXAMPLE
EXAMPLE
HERE IS A SIMPLE EXAMPLE
EXAMPLE
HERE IS A SIMPLE EXAMPLE
EXAMPLE
HERE IS A SIMPLE EXAMPLE
EXAMPLE
HERE IS A ...... EXAMPLE
EXAMPLE
HERE IS A SIMPLE EXAMPLE
EXAMPLE
HERE IS A SIMPLE EXAMPLE
EXAMPLE
HERE IS A SIMPLE EXA...E
EXAMPLE
HERE IS A SIMPLE EXAMPLE
Note that the KPM algorithm inspects every character passed before the
match was found.
[Return to String Searching Page]
[end of example]