[Feature]: Add a visualizer for the KMP (Knuth-Morris-Pratt) String Search algorithm #87
Description
So, what is it about?
📌 Description
Add a visualizer for the KMP (Knuth-Morris-Pratt) String Search algorithm.
This is a cornerstone of string-matching algorithms, and this feature will help users understand its two-phase process: pre-processing the pattern (building the LPS table) and efficiently searching the text.
✅ Expected Behavior
Input Panel: Allow users to enter a text string and a pattern string.
Two-Phase Visualization:
Phase 1: LPS Table Generation:
Visualize the pattern and the lps (Longest Proper Prefix which is also Suffix) table being built.
Highlight the i and len pointers as they compare characters to build the table.
Animate the lps table cells being filled.
Phase 2: Search:
Visualize the text string and the pattern string "sliding" underneath it.
Highlight the i (text pointer) and j (pattern pointer) as they compare.
Animate the "jumps" when a mismatch occurs, showing how lps[j-1] is used to shift the pattern.
Clearly highlight any full matches found in the text.
Explanation Panel: Show a human-readable log for both phases.
LPS Phase Example: "Comparing pattern[i] ('A') and pattern[len] ('B'). Mismatch. Falling back..."
Search Phase Example: "Mismatch at j=4. Jumping pattern: j = lps[j-1] = 2."
Control Panel: Include Play/Pause, Reset, Step-through (Prev/Next), and Speed controls.
🧩 Why This Is Needed
The KMP algorithm's efficiency comes from a clever "trick" (the LPS table) that is difficult to grasp from text alone.
Visualizing the LPS table's construction and use is the best way to understand why KMP is so fast.
It helps learners visualize:
The concept of pre-processing a pattern.
How to "jump" intelligently on a mismatch, avoiding re-checking characters.
A classic and highly efficient two-pointer algorithm.
Code of Conduct
- I agree to follow this project's Code of Conduct