How do you search for a pattern in a string (naive and KMP)?
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).