Pattern Matching: KMP & Z

The prefix function, KMP failure links, the Z-array, and periods and borders.

0 / 5 solved

Question Tags Difficulty Success

1. Filling The Prefix Table

kmpprefix-function +1

Medium —

2. Three Does Not Divide

kmpprefix-function +1

Medium —

3. Inside The Z Box

z-functionstring-matching +1

Medium —

4. Two Matches Gone Missing

kmpstring-matching +1

Medium —

5. Decrement Instead Of Jump

kmpprefix-function +1

Hard —

Learning Resources

cp-algorithms, Prefix function, Knuth-Morris-Pratt

cp-algorithms, Z-function

Algorithms, 4th Edition, Substring Search

Up next

5 of 5 questions here are still unsolved.

Next module Rolling Hash & Rabin-Karp