EXAMPLE
 HERE IS A SIMPLE EXAMPLE


By clicking on the linked character you can see how the Knuth-Pratt-Morris (KPM) algorithm searches in this example.

[Abort Search]











































  EXAMPLE
 HERE IS A SIMPLE EXAMPLE


Note 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.

[Abort Search]











































  EXAMPLE
 HERE IS A SIMPLE EXAMPLE


Note 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.

[Abort Search]











































    EXAMPLE
 HERE IS A SIMPLE EXAMPLE


[Abort Search]











































    EXAMPLE
 HERE IS A SIMPLE EXAMPLE


[Abort Search]











































      EXAMPLE
 HERE IS A SIMPLE EXAMPLE


[Abort Search]











































       EXAMPLE
 HERE IS A SIMPLE EXAMPLE


[Abort Search]











































        EXAMPLE
 HERE IS A SIMPLE EXAMPLE


[Abort Search]











































         EXAMPLE
 HERE IS A ...... EXAMPLE


[Abort Search]











































                  EXAMPLE
 HERE IS A SIMPLE EXAMPLE


[Abort Search]











































                  EXAMPLE
 HERE IS A SIMPLE EXAMPLE


[Abort Search]











































                  EXAMPLE
 HERE IS A SIMPLE EXA...E


[Abort Search]











































                  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]