How to use the KMP String Matching Visualizer
- 1. Set it upType the text (up to 60 characters) and the pattern (up to 20).
- 2. RunPress Search.
- 3. ReplayFirst watch the LPS table being built, then the matching, with the pattern aligned under the text.
Worked example
Searching for ABABCABAB in ABABDABACDABABCABAB finds one match at index 10. The pattern's LPS table is 0 0 1 2 0 1 2 3 4: for example, at index 3 the prefix "AB" is also a suffix of "ABAB", so LPS is 2. KMP makes 23 character comparisons; the naive method, which restarts the pattern at every position, makes 29 here, and far more on repetitive text such as many A's followed by a B.
How the shift works
When text[i] doesn't match pattern[j], the first j characters did match, so KMP already knows what that part of the text says. LPS[j − 1] tells it the longest prefix of the pattern that's also a suffix of what matched, so it can continue comparing from there without moving i backwards. That keeps the whole search at O(n + m) for text length n and pattern length m.
Related ideas
- The LPS table is the same as the prefix function used in competitive programming.
- Rabin-Karp uses hashing instead and suits searching many patterns at once.
- In everyday code, built-in methods like indexOf or str.find are usually fast enough.
- The Z-algorithm solves the same problem with a different table and is popular in competitive programming.
- Try a pattern like AAAB in a long run of A's to see KMP's advantage most clearly.
Frequently asked questions
What does LPS stand for?
Longest proper prefix that is also a suffix.
Is the search case-sensitive?
Yes. 'a' and 'A' are different characters.
Does it find overlapping matches?
Yes. After a match it continues using the LPS table, so overlapping occurrences are found.
Is the KMP visualizer free?
Yes. You can use the KMP visualizer without signing up. The first time you run it, we ask once for your name and WhatsApp number; after that the KMP visualizer and every other Uncodemy tool open straight away.