String Matching (KMP)

    DSA · Advanced

    Definition

    KMP finds a pattern in text in linear time using a prefix (LPS) table to avoid rechecking.

    Foundation of efficient text search.

    Diagram

    pattern: a b a bLPS: 0 0 1 2

    Flowchart

    Build LPS for patternScan textOn mismatch, jump using LPSOn full match, record index

    Example: LPS table

    p = 'ababaca'
lps, k = [0] * len(p), 0
for i in range(1, len(p)):
    while k and p[i] != p[k]: k = lps[k - 1]
    if p[i] == p[k]: k += 1
    lps[i] = k
print(lps)

    Output: [0, 0, 1, 2, 3, 0, 1]

    Complexity

    O(n + m)

    Key points

    • Rabin-Karp uses rolling hashes
    • Z-algorithm is an alternative

    Interview questions

    What does LPS store?

    Length of the longest proper prefix that is also a suffix at each position.

    More DSA topics

    ArraysLinked ListStackQueue