KMP String Matching

DSA · Classic Algorithms

Theory

The Knuth-Morris-Pratt (KMP) algorithm finds every occurrence of a pattern inside a text in O(n + m) time. The naive approach slides the pattern one position at a time and can recompare the same characters again and again, costing O(n * m). KMP avoids this by precomputing an LPS array (longest proper prefix that is also a suffix) for the pattern. When a mismatch happens after matching some characters, the LPS value tells how many of those characters are already known to match the start of the pattern, so the search continues without moving backwards in the text. Building the LPS array takes O(m) and scanning the text takes O(n).

Why we use it

Fast pattern search is used in text editors, search tools like grep, DNA analysis and log scanning. KMP is also a common interview topic that tests understanding of prefix functions.

When to use it

Use KMP when you need guaranteed linear-time search, especially for repetitive patterns or streaming text. In everyday Python, str.find and the re module are usually enough.

How it works

  1. Build LPS table for the pattern
  2. For each character in text
  3. Character matches pattern[j]? Yes: j = j + 1. No: If j > 0: j = lps[j-1], compare again.
  4. j == pattern length? Yes: Match found; j = lps[j-1]. No: Continue.
  5. O(n + m)

Syntax

Build LPS for pattern       O(m)
Scan text using LPS on mismatch O(n)
Total O(n + m)

Example

def build_lps(p):
    lps, length = [0] * len(p), 0
    for i in range(1, len(p)):
        while length and p[i] != p[length]:
            length = lps[length - 1]
        if p[i] == p[length]:
            length += 1
        lps[i] = length
    return lps

def kmp_search(text, p):
    lps, j, found = build_lps(p), 0, []
    for i, ch in enumerate(text):
        while j and ch != p[j]:
            j = lps[j - 1]
        if ch == p[j]:
            j += 1
        if j == len(p):
            found.append(i - j + 1)
            j = lps[j - 1]
    return found

print("LPS of ABABCABAB:", build_lps("ABABCABAB"))
print("Matches:", kmp_search("ABABDABACDABABCABAB", "ABABCABAB"))
print("Overlapping:", kmp_search("aaaaa", "aa"))
log = "ERROR disk ... INFO ok ... ERROR timeout"
print("ERROR at:", kmp_search(log, "ERROR"))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic