Algorithm Guidecomplexity: O(n + m)

KMP (Knuth-Morris-Pratt)

A string search that precomputes a failure function (LPS) so that, on a mismatch, it skips ahead instead of re-comparing the pattern from the start. It never rewinds the text pointer, matching in O(n+m).

01KMP (Knuth-Morris-Pratt)

Explore How It Works

KMP starts. The failure function LPS precomputes prefix info for 'ABABC', so on a mismatch the text never rewinds — only the pattern skips ahead.

Line the pattern up with the start of the text. The first four chars, ABAB, match right through.

The fifth char is where they part: the text has D, the pattern has C.

The AB ending the matched ABAB is also the pattern's own prefix. Pull the pattern forward by just that much — two cells — and it still misses.

There is no prefix left to reuse, so move the pattern five cells on. Never rewinding our place in the text is the heart of KMP.

At the new position all five chars, ABABC, match.

Search complete · the pattern starts at index 5. The text was never rewound, so it finishes in O(n+m).

text

pattern

Live Python

1def build_lps(pattern):

2 lps = [0] * len(pattern)

3 length, i = 0, 1

4 while i < len(pattern):

5 if pattern[i] == pattern[length]:

6 length += 1

7 lps[i] = length

8 i += 1

9 elif length:

10 length = lps[length - 1]

11 else:

12 lps[i] = 0

13 i += 1

14 return lps

16def kmp(text, pattern):

# lps = [0,0,1,2,0]

17 lps = build_lps(pattern)

18 i = j = 0

19 while i < len(text):

20 if text[i] == pattern[j]:

21 i += 1; j += 1

22 if j == len(pattern):

23 return i - j

24 elif j:

25 j = lps[j - 1]

26 else:

27 i += 1

28 return -1

1 / 7

02 Understand It Simply

For Everyone

🔑How It Works

Precomputes, for every prefix, where to resume after a mismatch. The text is therefore scanned once, never backtracked.

💡In Plain Words

Precomputes the pattern's failure function (LPS) so that on a mismatch it advances the pattern without rewinding the text.

No wasted comparisons — O(n+m).

📍Where It's Used

–Text search
–log and DNA-sequence matching
–grep-like tools

03 Python Implementation

A clean, readable reference implementation of the core logic of KMP (Knuth-Morris-Pratt).

core_implementation.py

def build_lps(pattern):
    lps = [0] * len(pattern)
    length, i = 0, 1
    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length:
            length = lps[length - 1]
        else:
            lps[i] = 0
            i += 1
    return lps

def kmp(text, pattern):
    lps = build_lps(pattern)
    i = j = 0
    while i < len(text):
        if text[i] == pattern[j]:
            i += 1; j += 1
            if j == len(pattern):
                return i - j
        elif j:
            j = lps[j - 1]
        else:
            i += 1
    return -1

04 Frequently Asked Questions

FAQ

What is KMP (Knuth-Morris-Pratt)?+

What is the time complexity of KMP (Knuth-Morris-Pratt)?+

The time complexity of KMP (Knuth-Morris-Pratt) is O(n + m). Follow the step-by-step visualization to see exactly why.

Where is KMP (Knuth-Morris-Pratt) used?+

Text search, log and DNA-sequence matching, grep-like tools.

What's a simple analogy for KMP (Knuth-Morris-Pratt)?+

Precomputes, for every prefix, where to resume after a mismatch. The text is therefore scanned once, never backtracked.

→ Strings — see allRelated