Linear String Pattern Matching Lab

Interactive evaluation of KMP Longest Prefix Suffix (LPS) fallback arrays and Rabin-Karp polynomial rolling hashes.

Linear String Pattern Matching

KMP Longest Prefix Suffix (LPS) Array Builder

Search Time: O(N + M) Zero Backtracking

Pattern String: "ABABCABAB"LPS[3] = 2

LPS Analysis for index 3:

Prefix substring: "ABAB". The longest proper prefix that is also a suffix is of length 2. If mismatch occurs at index 4, KMP skips directly to index 2 without rewinding the text pointer!

Modular Hash Matching Engine

Rabin-Karp Polynomial Rolling Hash Stepper

Window Hash: 1024

Target Pattern: "AAB" (Hash: 1428)Window [0..2]: "ABC"

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]