So algorithms aren't exactly my strong suit, and this is the frst time I've actually ever seen this improvement, but I'll give it a shot: basically, this will cause less backtracking in the search algorithm. The character that "breaks" the search is the only one that should require a backtrack.
So I will show a test string with the original KMP table and the improved table:
Code:
SLOTHS ARE SLOW AND SLEEPY
X0000000000012300000012000 (KMP)
X0000000000000300000002000 (improved)
With the improved algorithm, "SLOTHS ARE SNAZZY DRESSERS" will not require any backtracking, even though there is another 'S', but "SLOTHS ARE SLOPPY EATERS" will require a backtrack of 3 characters after the first 'P' in "SLOPPY" because the entire sub-pattern has been matched.
Hope that helps some. Again, algorithms aren't my strong suit, so maybe somebody else here can fill in any gaps which I may have left.
Bookmarks