</>EmbeddedInterview

How do you search for a pattern in a string (naive and KMP)?

MediumArrays & Strings (Coding Round)

Short answer: The naive method tries every starting position i and compares the pattern character by character: O(n·m) in the worst case. KMP precomputes, for each prefix of the pattern, how far it can fall back after a mismatch, so the text is never rescanned: O(n + m).

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

void search_naive(const char *text, const char *pat)
{
    size_t n = strlen(text), m = strlen(pat);
    if (m == 0 || m > n) return;            /* n - m would underflow with size_t */
    for (size_t i = 0; i <= n - m; i++) {
        size_t j = 0;
        while (j < m && text[i + j] == pat[j]) j++;
        if (j == m) printf("Pattern found at index %zu\n", i);
    }
}
/* text "geeksforgeeks", pattern "eks" -> indices 2 and 10 */

The size_t trap: strlen returns size_t. If the pattern is longer than the text, n - m wraps to a huge value and the loop reads far past the end. Check m > n first (or use signed int lengths as in many textbook versions).

KMP (Knuth–Morris–Pratt)

void search_kmp(const char *text, const char *pat)
{
    size_t n = strlen(text), m = strlen(pat);
    if (m == 0) return;
    size_t lps[m];                           /* longest proper prefix that is also a suffix */
    lps[0] = 0;
    for (size_t i = 1, len = 0; i < m; ) {
        if (pat[i] == pat[len])      lps[i++] = ++len;
        else if (len)                len = lps[len - 1];
        else                         lps[i++] = 0;
    }
    for (size_t i = 0, j = 0; i < n; ) {
        if (text[i] == pat[j]) {
            i++; j++;
            if (j == m) { printf("found at %zu\n", i - m); j = lps[j - 1]; }
        } else if (j) {
            j = lps[j - 1];                  /* fall back in the pattern, not the text */
        } else {
            i++;
        }
    }
}

When the naive method is worst: text "AAAAAAAAAB" with pattern "AAAB" compares almost the whole pattern at every position.

In practice: strstr() finds the first occurrence and libraries use fast algorithms. In firmware, the common case is matching short tokens in a UART stream (e.g. waiting for "OK\r\n" from a modem); a small KMP-style state machine processes one byte at a time as it arrives, with no buffering.

Other algorithms to name: Rabin–Karp (rolling hash, good for many patterns), Boyer–Moore (skips ahead, fast on long patterns).