String matching: naive search and KMP

Introduction

Ctrl+F in a browser, grep on a server and DNA searches in biology all solve the same problem: find every position where a pattern of length m appears in a text of length n.

Every editor has a Find command. Making it fast on awkward inputs is a neat problem, because the answer comes from noticing what a failed comparison has already told you.

How it works

The naive search

Put the pattern under the text at position 0 and compare character by character. On a mismatch, slide the pattern one place right and start again from its first character.

#include <stdio.h>
#include <string.h>

int main(void) {
    const char *text = "AABAACAADAABAABA";
    const char *pat = "AABA";
    int n = strlen(text), m = strlen(pat), compares = 0;
    for (int s = 0; s + m <= n; s++) {    // each shift of the pattern
        int j = 0;
        while (j < m) {
            compares++;
            if (text[s + j] != pat[j]) break;
            j++;
        }
        if (j == m) printf("found at %d\n", s);
    }
    printf("comparisons: %d\n", compares);
    return 0;
}

In the worst case (text AAAA…A, pattern AAA…AB) almost every shift compares nearly all m characters: O(n · m). The waste is that after a mismatch, it forgets everything it just learned about the text.

Other algorithms

• Rabin–Karp compares a rolling hash of each window with the pattern's hash, and checks characters only when the hashes match. Good for searching many patterns at once.
• Boyer–Moore compares from the pattern's end and can skip ahead by up to m characters, so on ordinary text it is often faster than reading every character. Tools like grep use ideas from it.
• The Z-algorithm computes, for each position, how long a match with the pattern's start begins there: another O(n + m) method.

Syntax

if (text[i] == pat[j]) j++;          // matched one more
else if (j > 0) j = lps[j - 1];      // slide the pattern; i stays put

Example

Suppose the pattern AABA matched AAB and then failed. The last matched character, A, is also how the pattern starts. So the pattern can slide until its first A sits under that A, and comparing continues from the pattern's second character: the text position never moves back.

How far to slide depends only on the pattern, so Knuth, Morris and Pratt (1977) compute it once, in a table:

lps[i] = the length of the longest proper prefix of pattern[0..i] that is also a suffix of it.

For AABA, lps[3] = 1 because the one-letter start A is also its end. During the search, after j characters matched and the next one fails, set j = lps[j − 1] and compare the same text character again.

#include <stdio.h>
#include <string.h>

int lps[20];

void build_table(const char *p, int m) {
    int len = 0;
    lps[0] = 0;
    for (int i = 1; i < m;) {
        if (p[i] == p[len]) lps[i++] = ++len;
        else if (len > 0) len = lps[len - 1];   // fall back to a shorter start
        else lps[i++] = 0;
    }
}

int main(void) {
    const char *text = "AABAACAADAABAABA";
    const char *pat = "AABA";
    int n = strlen(text), m = strlen(pat), compares = 0;
    build_table(pat, m);
    for (int i = 0, j = 0; i < n; i++) {
        while (1) {
            compares++;
            if (text[i] == pat[j]) {
                j++;
                break;
            }
            if (j == 0) break;
            j = lps[j - 1];                     // slide the pattern; i stays
        }
        if (j == m) {
            printf("found at %d\n", i - m + 1);
            j = lps[m - 1];                     // keep the overlap
        }
    }
    printf("comparisons: %d\n", compares);
    return 0;
}

The table takes O(m) to build, and the search O(n): every comparison either moves forward in the text or slides the pattern right, and each can happen at most n times. In total O(n + m), whatever the text looks like. The DSA Lab's String search tool runs both methods on your own text and counts their comparisons.

Line by line

1. lps is a global table, and build_table fills it from the pattern alone.
2. In build_table, len is the length of the current prefix that is also a suffix. A match extends it, and a mismatch falls back to lps[len - 1].
3. In main, i walks over the text, and j counts how many pattern characters match so far.
4. The inner loop compares. On a match, j grows. If j is already 0, it gives up on this text position.
5. Otherwise j falls back through the table, and the same text character is compared again.
6. When j reaches m, a full match ends at i, so it starts at i - m + 1. Then j = lps[m - 1] keeps any overlap.
7. The output lists the matches and the total comparisons, which you can compare with the naive method.

Expected result

found at 0
found at 9
found at 12
comparisons: 20

In the real world

Text editors, intrusion-detection systems that scan network traffic, and tools that search DNA data all need fast matching. Which algorithm they use varies, but each one avoids repeating work the same way KMP does.

Common mistakes

• After a full match, restarting at j = 0: that misses overlapping matches such as aa in aaaa. Continue with j = lps[m − 1].
• Moving the text index back after a mismatch: in KMP only j changes.
• Building lps with len = lps[len] instead of lps[len − 1].

Best practices

• Compute the lps table by hand for a short pattern before coding it.
• Test with overlapping matches, no matches, and a pattern as long as the text.
• Use your language's search function unless you have a measured reason not to.

Summary

String matching finds every place a pattern occurs in a text. The naive method can take O(n · m), while KMP uses the lps table to avoid moving back in the text, and it takes O(n + m) in all.

Mark lesson complete