Loading algorithms…

Loading visualizer…

Algorithms/Searching/KMP String Matching

KMP String Matching

Find a pattern in text in linear time by never re-examining text characters — the failure (LPS) table remembers how much of the pattern already matched.

StringsLPS TableNo Backtracking
Phase 1 · Build LPS

Text

A
0
B
1
A
2
B
3
D
4
A
5
B
6
A
7
C
8
D
9
A
10
B
11
A
12
B
13
C
14
A
15
B
16
A
17
B
18

Pattern

A
0
B
1
A
2
B
3
C
4
A
5
B
6
A
7
B
8

LPS table (i = 1)

·
0
·
1
·
2
·
3
·
4
·
5
·
6
·
7
·
8
Step 1 of 37: Phase 1 — build the failure (LPS) table for "ABABCABAB": for every prefix, the length of its longest proper prefix that is also a suffix.
1 / 37
Speed

Phase 1 — build the failure (LPS) table for "ABABCABAB": for every prefix, the length of its longest proper prefix that is also a suffix.

Matches found
0
Comparisons so far
0
kmp.js
1function buildLPS(pattern) {
2 const lps = [0];
3 let len = 0, i = 1;
4 while (i < pattern.length) {
5 if (pattern[i] === pattern[len])
6 lps[i++] = ++len;
7 else if (len > 0)
8 len = lps[len - 1]; // fall back
9 else lps[i++] = 0;
10 }
11 return lps;
12}
13 
14function kmpSearch(text, pat) {
15 const lps = buildLPS(pat);
16 let i = 0, j = 0; // text / pattern
17 const hits = [];
18 while (i < text.length) {
19 if (text[i] === pat[j]) {
20 i++; j++;
21 if (j === pat.length) {
22 hits.push(i - j);
23 j = lps[j - 1];
24 }
25 } else if (j > 0) {
26 j = lps[j - 1]; // slide pattern
27 } else i++; // advance text
28 }
29 return hits;
30}

Phase 1 builds the LPS table, Phase 2 scans — watch j fall back while i never rewinds

About the KMP String Matching algorithm

Find a pattern in text in linear time by never re-examining text characters — the failure (LPS) table remembers how much of the pattern already matched.

Category
Searching
Difficulty
Medium
Time complexity
O(n+m)
Space complexity
O(m)
Introduced
1977
←Previous Algorithm
Linear Search
SearchingO(n)
Next Algorithm→
Fibonacci (Memoization)
O(n)Dynamic Programming