The Knuth–Morris–Pratt string searching algorithm (or KMP algorithm) searches for occurrences of a “word” $W$ within a main “text string” $T$ by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters.

Complexity

  • Time: $O( W + T )$ (much faster comparing to trivial $O( W \times T )$)
  • Space: $O( W )$

References

Implementations

  • 1

    # TODO: Implement in Python

  • 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

    const string = "AAAABAABAAAABAAABAAAA";
const pattern = "AAAABAAA";

let _next = Array(...Array(pattern.length)).map(Number.prototype.valueOf, 0);

function get_next(pattern)
{
    let q = 1; // postfix pointer
    let k = 0; // prefix pointer
    
    for (; q < pattern.length; ++q)
    {
        
        while ((k > 0) && (pattern[q] !== pattern[k]))
        {
            
            k = _next[k - 1];
        }
        if (pattern[q] === pattern[k])
        {
            
            ++k;
        }
        
        _next[q] = k;
    }
    
}

function KMP(string, pattern)
{
    const match_positions = [];
    let match_start_position;

    let i = 0; // string pointer
    let k = 0; // pattern pointer
    get_next(pattern);
    for (; i < string.length; i++)
    {
        
        while ((k > 0) && (string[i] != pattern[k]))
        {
            
            k = _next[k - 1];
        }
        if (string[i] === pattern[k])
        {
            ++k;
            if (k === pattern.length)
            {
                match_start_position = i - pattern.length + 1;
                match_positions.push(match_start_position);
                
                k = _next[k - 1];
            }
            else
            {
                
            }
        }
        else
        {
            
        }
        
    }
    
}

KMP(string, pattern);