KMP Scanner
Easy Hunt
P="AB" in "ABABAB"
Medium Hunt
P="ABA" in "ABABAABA"
Hard Hunt
P="ABAB" in "ABABCABABABAB"
📎 Concatenated String: Pattern + '#' + Text
🛡️ PSI/LPS Array (Pattern prefix)
🗺️ Hunting Ground (Text)
🎯 Hunt Results
Matches Found: 0
Start the hunt to find monsters!
📜 Hunt Log
Enter pattern and text, then click "Start Hunt"
💡 KMP Algorithm Implementation
function KMPSearch(pattern, text) { // Step 1: Build LPS array for the
pattern const lps = buildLPS(pattern); // Step 2: Concatenate: pattern
+ '#' + text const concat = pattern + '#' + text; // Step 3: Build PSI
array for concatenated string const psi = buildLPS(concat); // Step 4:
Find matches where PSI[i] === pattern.length const matches = []; const
patternLen = pattern.length; for (let i = patternLen + 1; i <
concat.length; i++) { if (psi[i] === patternLen) { // Match found!
Calculate position in original text const textPos = i - 2 *
patternLen; matches.push(textPos); } } return matches; } function
buildLPS(str) { const n = str.length; const lps = new
Array(n).fill(0); let len = 0; let i = 1; while (i < n) { if (str[i]
=== str[len]) { len++; lps[i] = len; i++; } else { if (len !== 0) {
len = lps[len - 1]; } else { lps[i] = 0; i++; } } } return lps; }