Summary - String matching

Print the match index with KMP in a mini task.

Summary - String matching

In this group we covered five string matching methods: KMP, Rabin-Karp, Boyer-Moore, Z-algorithm and suffix array.

KMP uses a prefix table, Rabin-Karp a rolling hash, Boyer-Moore the bad character rule, all in linear time. The Z-algorithm and suffix array support broader tasks.

We will now revisit KMP with a small task.

Exercise kmp_search mini task

Write kmp_search(text, pattern). Return the first match index, or -1. Print 1 with print(kmp_search("mississippi", "issi")).

Show example solution

def kmp_search(text, pattern):
    # First match with KMP
    n, m = len(text), len(pattern)
    lps = [0] * m
    length = 0
    i = 1
    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    i = j = 0
    while i < n:
        if text[i] == pattern[j]:
            i += 1
            j += 1
            if j == m:
                return i - j
        else:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    return -1
print(kmp_search("mississippi", "issi"))

Test yourself

Which method has no hash collision risk?
- Rabin-Karp
- Boyer-Moore bad character
- KMP
- Rolling hash
Show answer

KMP — KMP does not use hashing, so no collision risk.

KMP lps value

# pattern = "abcabd"
# lps[4] = ____

Show answer

# pattern = "abcabd"
# lps[4] = 2

Method-property

KMP

Prefix table
Rabin-Karp

Rolling hash
Boyer-Moore

Bad character
Z-algorithm

Z-array

Next lesson: Vector cross product

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies