Knuth-Morris-Pratt (KMP) Algorithm
Efficient string matching algorithm that uses a failure function (LPS array) to avoid re-examining characters.
LPS Array (Longest Prefix Suffix)
A
0
B
0
A
0
B
0
C
0
A
0
B
0
A
0
B
0
ABABDABACDABABCABAB
ABABCABAB
Status: Enter text and pattern to start
1function KMP(text, pattern):
2 lps = computeLPS(pattern)
3 i = 0, j = 0
4 while i < n:
5 if pattern[j] == text[i]:
6 i++, j++
7 if j == m:
8 print "Found at " + (i-j)
9 j = lps[j-1]
10 else if i < n and pattern[j] != text[i]:
11 if j != 0: j = lps[j-1]
12 else: i++
Complexity
TimeO(N + M)
SpaceO(M)
Where N is text length, M is pattern length. Guaranteed linear time.