The LPS Forge
Pointer i (current position)
-
Pointer x (length of prev LPS)
-
🛡️ Forged Shield
🛡️
Awaiting forging...
📊 LPS Array Table
📜 Forging Log
Enter a string and click "Forge Shield" to see the LPS construction
💡 LPS Array Construction Algorithm
function buildLPSArray(pattern) { const n = pattern.length; const lps
= new Array(n).fill(0); let i = 1; // Current position in pattern let
x = 0; // Length of previous longest prefix suffix while (i < n) { if
(pattern[i] === pattern[x]) { // Characters match x++; lps[i] = x;
i++; } else { // Characters don't match if (x !== 0) { // Fall back
using the LPS array x = lps[x - 1]; // KEY: Move x back using LPS[x-1]
} else { // No fallback possible lps[i] = 0; i++; } } } return lps; }
// The LPS[i] value represents: // Length of longest proper prefix of
pattern[0..i] // which is also a suffix of pattern[0..i]