Kmp pattern matcher

[11jmb]

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:

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.

[DaviesX]

Thank you very much !
Because of your test, now I get it
(Actually, the array would have 1 more elements then the strings one)

Because once the element become unequal, for example,
SLOW and
SLA....

although I can backtrack to 2, but it still using "O" compare to "A" untill it backtracks to the original point (if using the original method). So the improved one cleverly backtrack one more time before they used to do the actual compare.(Every equal element do so)

prefix[current] = form;  vs
prefix[current] = prefix[form];

That is my thought about it. Thank you one more time ^_^

[11jmb]

Thank you very much !
(Actually, the array would have 1 more elements then the strings one)

I think you can implement the algorithm with a backtracking array the same length as your character array (nut including the null). Perhaps I misunderstood the algorithm, and did not sufficiently test with a case which required an extra value in the backtracking array.

Also, note that in my previous post, the X in the backtracking arrays woulds be implemented as a -1. I wanted the text to line up, and didn't do a good job of explaining that.

[DaviesX]

Yeah, the last one may needed in real implementation to avoid border checking or you have to -1 when mismatched, although it is useless...

[DaviesX]

Btw, this algorithm is worthy to read rather than worthy to use. It is slower than the plain algorithm when the pattern is short although its theoretical time complexity is linear LOL