Searching for a substring

Overview

Substring search answers a very ordinary question: does this text contain that word, and if so, where? You do it every time you press Ctrl-F in a browser, and programs do it constantly under the hood.

The big string you search in is called the haystack. The small string you look for is the needle. Search returns either the location of the first match or a clear "not found" signal.

This lesson builds directly on two things you already know. From C strings you know that a C string is just a char array ending in a '\0' (NUL) byte, and that the standard library uses that NUL to know where the string stops. From Implementing strlen you know how to walk a string one byte at a time until you hit that NUL. Substring search is the natural next step: instead of walking to measure length, you walk to compare, sliding the needle along the haystack and checking for a match at each position.

The standard library gives you strstr for NUL-terminated text and memmem (a GNU/BSD extension) for raw byte buffers. We will use both, and also write the search by hand so the mechanism is never a mystery.

Why it matters

Almost every program that touches text eventually asks "does this contain X?" Log analysers filter lines that mention an error code. Web servers route a request by looking for a path prefix in the URL. Config loaders check whether a setting names a deprecated option. Network code scans a payload for a header or a marker.

The operation is so common that getting it slightly wrong is expensive in two directions. Get the logic wrong — mishandle an empty needle, or read past a buffer that was not NUL-terminated — and you get crashes or wrong answers. Get the performance wrong and it does not matter on a 40-byte line, but on a multi-gigabyte log or a packet-capture file the difference between a naive scan and a smart algorithm is the difference between milliseconds and minutes. Knowing what strstr actually does lets you make that call deliberately instead of by accident.

Core concepts

1. Haystack, needle, and the return value

Definition. strstr(haystack, needle) returns a pointer to the first character of the first place needle appears inside haystack, or NULL if it never appears.

The return type is a pointer into the haystack, not a copy and not an index. That is a deliberate design choice: from the pointer you can keep working with the rest of the string, and you can compute an index yourself.

haystack:  "the cat sat"
            ^0  ^4
needle:    "cat"

strstr returns ----> &haystack[4]
offset = returned_ptr - haystack = 4

How it works internally. The library slides the needle along the haystack. At each starting position it compares character by character; on a mismatch it advances the start by one and tries again; if it reaches the needle's NUL with everything matching, that start position is the answer.

When to use it / when NOT to. Use strstr for ordinary NUL-terminated C strings. Do not use it on data that may contain embedded NUL bytes (binary files, some network reads) — it will stop at the first NUL and miss anything after it.

Pitfall. Beginners test the return value as if it were an index: if (strstr(...) == 0) looks like "found at index 0" but NULL is 0, so this actually means "not found." A real match at offset 0 returns a non-NULL pointer.

Knowledge check: strstr("hello", "lo") returns a pointer. What integer offset does that pointer correspond to, and how would you compute it?

2. Empty needle and other edge cases

The C standard says: if needle is the empty string "", strstr returns the haystack pointer (offset 0). The empty string is considered to occur at the very start.

Pitfall. If you hand strstr a needle that came from untrusted input and it might be empty, your "count how many times it appears" loop can spin forever, because a match of length 0 never advances the pointer. Always decide what an empty needle means before the loop.

Knowledge check (predict the output): what does printf("%d\n", strstr("abc", "") == NULL); print — 0 or 1?

3. The naive algorithm and its cost

Definition. The naive (brute-force) search tries the needle at every position of the haystack.

haystack: A B A B A B C
needle:   A B A B C

pos 0:  A B A B C ?  ->  ABAB match, C vs A mismatch
pos 1:  _ A B A B C   ->  A vs B mismatch immediately
pos 2:  _ _ A B A B C ->  ABAB match, C vs A mismatch
...

Cost. If the haystack has n characters and the needle has m, the worst case is about n*m comparisons — written O(n*m). In practice most positions fail on the first character, so it is usually far faster than the worst case, which is why strstr in many libraries is just a tuned naive scan.

When to use / when NOT to. Naive is perfect for short needles and modest haystacks — which covers the vast majority of everyday code. Reach for a smarter algorithm only when profiling shows the search is a real bottleneck on large inputs.

Pitfall. Forgetting to stop early. If you do not check pos + m <= n, the inner compare can read past the end of the haystack.

4. Faster algorithms: KMP, Boyer-Moore, Aho-Corasick

These pre-process the needle so the search can skip work.

Tools like YARA and ClamAV use Aho-Corasick variants to scan for thousands of signatures at once. You rarely hand-write these; you use them when the standard strstr is provably too slow.

Knowledge check (explain in your own words): why can Boyer-Moore be sub-linear — that is, look at fewer characters than the haystack has — when the naive scan cannot?

5. strstr vs memmem

memmem(h, hn, n, nn) is the same idea but you pass explicit lengths, so it does not rely on NUL termination and can search binary data.

strstr:  stops at first '\0'   -> text only
memmem:  scans exactly hn bytes -> binary safe, NULs allowed

Note that memmem is a GNU/BSD extension, not standard C — portable code may need a fallback. This is exactly the distinction the existing quiz points at.

Syntax notes

#include <string.h>

/* Standard C: NUL-terminated text. */
char *strstr(const char *haystack, const char *needle);
/* Returns pointer to first match inside haystack, or NULL. */

/* GNU/BSD extension: raw bytes, explicit lengths. */
void *memmem(const void *haystack, size_t haystacklen,
             const void *needle,   size_t needlelen);

Turning a match into an offset uses pointer subtraction, whose result type is ptrdiff_t (print with %td):

const char *p = strstr(hay, needle);
if (p != NULL) {
    ptrdiff_t offset = p - hay;   /* distance in chars from the start */
    printf("found at offset %td\n", offset);
}

Key points: always compare the result against NULL before using it, and never dereference a NULL return.

Lesson

C's standard strstr finds the first occurrence of the needle in the haystack. It uses a naive O(n*m) scan.

For larger inputs, use Boyer-Moore or KMP, which run sub-linear or linear on average.

For multi-pattern search, use Aho-Corasick.

Code examples

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

/* Our own naive substring search, returning a 0-based index or -1.
   Kept separate from strstr so the mechanism is visible. */
int index_of(const char *hay, const char *needle) {
    if (hay == NULL || needle == NULL) return -1;

    size_t n = strlen(hay);
    size_t m = strlen(needle);

    if (m == 0) return 0;        /* empty needle matches at the start */
    if (m > n)  return -1;       /* needle can't fit -> no match */

    /* Only start where the needle could still fit: pos <= n - m. */
    for (size_t pos = 0; pos + m <= n; pos++) {
        size_t k = 0;
        while (k < m && hay[pos + k] == needle[k]) {
            k++;                 /* characters matched so far */
        }
        if (k == m) return (int)pos;  /* full needle matched */
    }
    return -1;                   /* fell off the end: not found */
}

int main(void) {
    const char *log = "GET /admin HTTP/1.1";

    /* 1. Standard library search. */
    const char *p = strstr(log, "/admin");
    if (p != NULL) {
        printf("strstr: found '/admin' at offset %td\n", p - log);
    } else {
        printf("strstr: not found\n");
    }

    /* 2. Our hand-written search, cross-checked against strstr. */
    int idx = index_of(log, "/admin");
    printf("index_of: '/admin' -> %d\n", idx);
    printf("index_of: 'DELETE' -> %d\n", index_of(log, "DELETE"));
    printf("index_of: ''       -> %d\n", index_of(log, ""));

    return 0;
}

What it does. It searches the request line "GET /admin HTTP/1.1" twice: once with the library strstr, once with our own index_of. /admin starts right after GET (4 characters: G, E, T, space), so both report offset 4. DELETE never appears, so index_of returns -1. The empty needle returns 0 by convention.

Expected output:

strstr: found '/admin' at offset 4
index_of: '/admin' -> 4
index_of: 'DELETE' -> -1
index_of: ''       -> 0

Edge cases handled: NULL inputs return -1 instead of crashing; a needle longer than the haystack short-circuits to -1; the pos + m <= n bound stops us reading past the end; the empty needle is defined to return 0.

Line by line

Walking index_of("GET /admin HTTP/1.1", "/admin"):

1. hay and needle are both non-NULL, so we skip the guard.
2. n = strlen(hay) is 19; m = strlen(needle) is 6.
3. m == 0? No. m > n? No (6 <= 19). So we enter the loop.
4. The loop tries each start pos while pos + 6 <= 19, i.e. pos from 0 up to 13.
5. At each pos, the inner while compares hay[pos+k] with needle[k], incrementing k on each match, stopping at the first mismatch or when k == m.
6. When k reaches m (all 6 characters matched), we return pos.

Trace of the inner loop at the key positions:

For "DELETE", no start position ever matches the first character D in a way that completes the needle, the loop runs to the end, and control falls through to return -1. For the empty needle, m == 0 triggers the early return 0 before the loop even starts, matching strstr's behaviour.

Common mistakes

1. Treating the return value as an index.

/* WRONG */
if (strstr(line, "error") == 0)   /* '== 0' means '== NULL' */
    puts("found at start");        /* nope: this branch means NOT found */

strstr returns a pointer. Comparing to 0/NULL tests found-vs-not-found, never position.

/* CORRECT */
const char *p = strstr(line, "error");
if (p != NULL)
    printf("found at offset %td\n", p - line);

Recognise it: you get "found"/"not found" backwards, or an offset of 0 wherever a match happens.

2. Infinite loop on an empty needle when counting.

/* WRONG: needle "" matches at every position and p never advances */
while ((p = strstr(p, needle)) != NULL) { count++; p += strlen(needle); }

If needle is "", strlen(needle) is 0, so p never moves and the loop hangs.

/* CORRECT: reject the empty needle up front, and always advance by >= 1 */
if (needle[0] == '\0') return 0;
size_t step = strlen(needle);
while ((p = strstr(p, needle)) != NULL) { count++; p += step; }

3. Using strstr on non-NUL-terminated data.

/* WRONG: buf came from read() and is NOT NUL-terminated */
ssize_t got = read(fd, buf, sizeof buf);
if (strstr(buf, "MZ")) ...   /* reads past 'got' bytes -> UB */

/* CORRECT: use lengths, not NUL termination */
if (memmem(buf, (size_t)got, "MZ", 2)) ...

Prevent it: the moment data comes from a socket or file read, track its length and search by length.

4. Off-by-one in a hand-written scan. Using pos < n instead of pos + m <= n lets the inner compare walk past the end of the haystack, reading uninitialised or out-of-bounds memory.

Debugging tips

Compiler / linker errors

• implicit declaration of function 'memmem' or an undefined reference at link time: memmem is a GNU extension. Define #define _GNU_SOURCE before including <string.h> on Linux, or provide your own fallback for portability.
• format '%td' expects argument of type 'ptrdiff_t': you printed a pointer difference with %d. Use %td for ptrdiff_t.

Runtime errors

• Segfault when using the result: you dereferenced a NULL return. Always check if (p != NULL) first.
• Reading garbage or a crash on binary data: strstr ran past an embedded NUL or an unterminated buffer. Switch to memmem with an explicit length.

Logic errors

• Match reported at the wrong place: print the offset and the ~20 characters around it so you can eyeball the hit instead of trusting the number.
• Count is off by one or infinite: check how you advance after each match (by strlen(needle) for non-overlapping, by 1 for overlapping) and confirm you handled the empty needle.

Questions to ask when it misbehaves

• Is my data actually NUL-terminated, or did it come from a raw read?
• Could the needle be empty or longer than the haystack?
• Am I comparing the pointer to NULL, or accidentally to an index?
• Does my loop bound guarantee pos + m <= n?

Memory safety

Substring search is a classic place for out-of-bounds reads, so keep these in mind.

• Termination vs length. strstr trusts the '\0'. If the haystack is not actually NUL-terminated (data from read/recv, a fixed-size field, mmaped memory), strstr keeps reading past the buffer — undefined behaviour that can crash or leak adjacent memory. Use memmem with the real byte count for anything that is not a genuine C string.
• Bounds in hand-written scans. Your inner comparison must never index beyond the haystack. The pos + m <= n guard in the example is what makes the hay[pos + k] access safe for all valid k.
• Empty needle. Define its meaning explicitly; an undefined empty-needle case leads to infinite loops in counting code (a denial-of-service if the needle is attacker-controlled).
• Overflow with lengths. When you compute n - m or pos + m, do it in a way that cannot underflow/overflow. Comparing pos + m <= n (both size_t) is safe here because we already ruled out m > n; writing pos <= n - m would underflow if m > n.
• const correctness. Take const char * parameters for inputs you only read. It documents intent and lets the compiler catch accidental writes.

Though this lesson is not tagged security, substring matching is the engine inside log scanners and simple detectors, so treating every buffer's length as untrusted is a good habit to carry into that work.

Real-world uses

Concrete uses. grep and editor "Find" are substring search at their core. Web servers match a URL prefix to route a request. Log pipelines (grep, journald filters, SIEM rules) flag lines that contain an error signature. Antivirus and IDS engines (ClamAV, Snort, YARA) scan payloads for many byte patterns at once using multi-pattern search. Databases use it for LIKE '%x%' queries, and shells use it for pattern tests.

Best-practice habits

Beginner:

• Always check the return against NULL before using it.
• Use clear names (hay, needle, offset) and const on read-only parameters.
• Decide up front what an empty needle and a not-found result mean, and test both.

Advanced:

• Match the tool to the input: plain strstr/memmem for small inputs; a pre-processing algorithm (KMP/Boyer-Moore) only when profiling proves it is the bottleneck; Aho-Corasick for many patterns.
• Track buffer lengths end-to-end; prefer length-taking APIs for anything from I/O.
• Consider case-folding and encoding (UTF-8) explicitly rather than assuming ASCII.
• Benchmark on representative data before optimising — the naive scan wins more often than beginners expect.

Practice tasks

1. Beginner — Offset reporter. Write a program that reads a needle and a haystack (hard-coded is fine) and prints either found at offset N or not found, using strstr and %td. Requirements: handle the not-found case without dereferencing NULL. Concepts: strstr, pointer subtraction.

2. Beginner — Contains check. Implement int contains(const char *hay, const char *needle) returning 1 if needle appears in hay, else 0. Return 1 for an empty needle (it always "appears"). Example: contains("hello", "ell") -> 1, contains("hello", "xyz") -> 0. Concepts: strstr, NULL check, empty-needle rule.

3. Intermediate — Count non-overlapping occurrences. Implement int count_occurrences(const char *hay, const char *needle) returning how many non-overlapping times needle appears. Example: count_occurrences("aaaa", "aa") -> 2. Requirements: reject the empty needle (return 0) so you never loop forever; advance by strlen(needle) after each hit. Hint: keep a moving pointer and call strstr from it. Concepts: looping with strstr, empty-needle safety.

4. Intermediate — Case-insensitive search. Write int index_of_ci(const char *hay, const char *needle) returning the 0-based index of the first case-insensitive match or -1. Example: index_of_ci("Hello", "ELL") -> 1. Hint: adapt the naive scan and compare with tolower((unsigned char)c) on both sides. Constraint: do not modify the input strings. Concepts: naive scan, <ctype.h>.

5. Challenge — Binary-safe finder. Implement long find_bytes(const unsigned char *hay, size_t hn, const unsigned char *needle, size_t nn) returning the offset of the first match or -1, working correctly when either buffer contains 0x00 bytes. Requirements: do not rely on NUL termination; guard pos + nn <= hn; return 0 for an empty needle. Hint: this is memmem written by hand — use memcmp for each window. Concepts: length-based search, bounds safety, memcmp.

Summary

Substring search finds a needle inside a haystack. In C, strstr(hay, needle) returns a pointer to the first match or NULL; subtract the haystack pointer to get a 0-based offset (%td). It walks the haystack with a naive O(n*m) scan, which is fast enough for almost all everyday text.

Most important syntax: char *strstr(const char *hay, const char *needle); (NUL-terminated) and void *memmem(...) with explicit lengths (binary-safe, GNU/BSD).

Common mistakes: comparing the return value as if it were an index, looping forever on an empty needle, and running strstr past an unterminated or embedded-NUL buffer.

Remember: always check for NULL first; decide what an empty needle means; use length-based memmem/your own bounded scan for raw bytes; and only reach for KMP, Boyer-Moore, or Aho-Corasick when a real measurement says the naive search is too slow.

Practice with these exercises

• Index of a substring
• Count occurrences
• Implement strstr
• Final Project: mini-grep — substring match in lines
• Detect weak crypto algorithm names
• Find dangerous C functions in toy source