Substring search by hand in C

The naive scan, written out, because knowing the cost is the point.

long find_substring(const char *text, const char *pattern) {
    size_t n = strlen(text);
    size_t m = strlen(pattern);
    if (m == 0) {
        return 0;
    }
    for (size_t start = 0; m <= n && start + m <= n; start++) {
        size_t i = 0;
        while (i < m && text[start + i] == pattern[i]) {
            i++;
        }
        if (i == m) {
            return (long) start;
        }
    }
    return -1;
}

How it works

1. Every starting position is tried in turn.
2. The worst case is the pattern length times the text length.
3. Bounding the outer loop avoids reading past the end.

Keywords and builtins used here

• char
• const
• find_substring
• for
• if
• long
• return
• size_t
• while

The run, in numbers

Lines

17

Characters to type

321

Tokens

118

Three-star pace

100 tpm

At the three-star pace of 100 tokens a minute, this run takes about 71 seconds.

Type this snippet

Step 3 of 3 in Comparing & searching, step 7 of 13 in Strings & text.

← Previous Next →