String Search Algorithms: Naive, KMP, Rabin-Karp, Aho-Corasick and .NET's IndexOf/SearchValues<string>

Version note: The code in this post was built with .NET 10 and C# 14 and verified with xUnit v3 4.0.2 tests; measurements were taken with BenchmarkDotNet 0.15.8.

Guess First

In a text made of 10,000 letter "a"s, we search for a 100-character pattern of 99 "a"s followed by a "b". The pattern is not in the text. The most straightforward algorithm tries every start position, slides one step right at the first mismatching character and compares the pattern from the start again. How many character comparisons does it make: around 10,000, 20,000, or a million?

Second question: Bookstore, the online bookstore used as the shared example across this site's series, checks book reviews against a 500-word banned list before publishing them. Between calling a separate Contains for each word and a structure that searches the whole list at once, how big a difference do you expect?

Naive Search and Its Worst Case

// Try every start position; on a mismatch, slide by one and start the pattern over
public static int IndexOf(string text, string pattern, out long comparisons)
{
    comparisons = 0;
    for (int start = 0; start <= text.Length - pattern.Length; start++)
    {
        int j = 0;
        while (j < pattern.Length)
        {
            comparisons++;
            if (text[start + j] != pattern[j]) break;
            j++;
        }

        if (j == pattern.Length) return start;
    }

    return -1;
}

text n=10000, pattern m=100
naive comparisons: 990,100
KMP comparisons:   19,901

Close to a million: 100 comparisons at each of 9,901 start positions. Naive search's worst case is O(n·m); the "around 10,000" you may have guessed is what you usually see on real text, because a mismatch typically happens at the first character or two. What worst case means and why it is considered separately is in the Big-O and Complexity series post "What Is Big-O Notation: Growth Rate, O, Ω, Θ and Worst Case". The problem is that, on user-controlled input, an attacker can produce the worst case: a review made of repeated characters and a repeating pattern.

KMP: Never Going Back in the Text

Naive search wastes work because it forgets what it learned after 99 characters matched. The algorithm Knuth, Morris and Pratt published in 1977, KMP for short, keeps that information: for every prefix of the pattern it precomputes the length of the longest part that is both a prefix and a suffix of it. This is called the failure function (or prefix function):

// failure[i] = length of the longest proper prefix of pattern[..(i + 1)] that is also its suffix
public static int[] BuildFailure(string pattern)
{
    int[] failure = new int[pattern.Length];
    int k = 0;
    for (int i = 1; i < pattern.Length; i++)
    {
        while (k > 0 && pattern[i] != pattern[k]) k = failure[k - 1];
        if (pattern[i] == pattern[k]) k++;
        failure[i] = k;
    }

    return failure;
}

failure("ababaca") = [0, 0, 1, 2, 3, 0, 1]

The value for the prefix "ababa" is 3: "aba" is both at the start and at the end. If 5 characters match during the search and the sixth fails, instead of restarting the pattern we continue with "3 characters already match". The index i in the text never moves back:

for (int i = 0; i < text.Length; i++)
{
    while (k > 0 && text[i] != pattern[k])
    {
        comparisons++;
        k = failure[k - 1]; // fall back inside the pattern; i never moves back
    }

    comparisons++;
    if (text[i] == pattern[k]) k++;
    if (k == pattern.Length)
    {
        matches.Add(i - k + 1);
        k = failure[k - 1];
    }
}

19,901 comparisons on the same input: below 2n. KMP's cost is O(n + m), and that is a guarantee; it does not matter how bad the input is. Because we continue with k = failure[k - 1] after a match, it also finds overlapping matches: 0, 1 and 2 for "aa" in "aaaa".

Rabin-Karp: Multiple Patterns with a Rolling Hash

Rabin and Karp's 1987 idea is to compare hashes instead of characters. A window of length m slides over the text; the window's hash is updated in O(1) by removing the contribution of the character that leaves and adding the one that enters (a rolling hash). When the hash matches we verify with a real comparison, because two different strings can have the same hash:

ulong window = Hash(text.AsSpan(0, m));
for (int start = 0; ; start++)
{
    if (byHash.TryGetValue(window, out List<string>? candidates))
    {
        foreach (string c in candidates)
        {
            if (text.AsSpan(start, m).SequenceEqual(c)) matches.Add((start, c));
        }
    }

    if (start + m == text.Length) break;
    // Roll: remove text[start], shift, add text[start + m]
    window = AddMod(window, Mod - MulMod(text[start], highPower));
    window = AddMod(MulMod(window, Base), text[start + m]);
}

We used 2⁶¹−1, a Mersenne prime, as the modulus; the product is computed with UInt128 so it cannot overflow. Rabin-Karp's real strength is in byHash: we can put the hashes of thousands of same-length patterns into a Dictionary and scan the text in a single pass. Plagiarism detection is exactly this: we turn every 20-character window of the original text into a pattern and search for them in the submitted text.

103 windows of 20 chars, 37 matching positions in the submission
copied: " his family takes control of the desert planet Arrakis, "

The average cost is O(n + m); if hashes collide often, the worst case is O(n·m) again. A good modulus and real verification prevent that in practice, but the guarantee is not deterministic as it is with KMP.

Aho-Corasick: A Trie and Failure Links

The words in the banned list have different lengths; Rabin-Karp struggles here. The algorithm Aho and Corasick developed in 1975 for a bibliographic search tool applies KMP's failure idea to the trie from the fourteenth post of this series. All patterns are added to a trie; then, for every node, we compute the answer to "if I cannot advance by one character from here, which node corresponds to the longest suffix of what I have read so far?", the failure link:

// Breadth-first: a node's failure link always points to a shallower node, which is already finished
private void BuildFailureLinks()
{
    Queue<int> queue = new();
    foreach (int child in _next[0].Values) queue.Enqueue(child); // depth 1 fails to the root
    while (queue.Count > 0)
    {
        int node = queue.Dequeue();
        foreach ((char c, int child) in _next[node])
        {
            int f = _fail[node];
            while (f != 0 && !_next[f].ContainsKey(c)) f = _fail[f];
            _fail[child] = _next[f].TryGetValue(c, out int target) && target != child ? target : 0;
            _output[child].AddRange(_output[_fail[child]]); // "she" also reports "he"
            queue.Enqueue(child);
        }
    }
}

The search is the trie version of KMP's loop: if there is no transition, follow the failure link; otherwise advance and report the patterns that end at that node. The classic example from the paper is the patterns he, she, his and hers with the text "ushers":

ushers -> she@1, he@2, hers@2

The same structure in Bookstore's review moderation:

string[] banned = ["scam", "casino", "free money", "click here", "spam"];
AhoCorasick ac = new(banned);
string review = "Great book! Not a scam. Click here for free money at our casino.";
foreach ((int index, string word) in ac.FindAll(review.ToLowerInvariant()))
    Console.WriteLine($"{index,3}: {word}");

 18: scam
 24: click here
 39: free money
 57: casino

Finding author names in a book description is the same job. If both "Jane Austen" and "Austen" are in the list, both are reported; which one to keep (longest match, first match) is your decision:

 24: Mary Shelley
 41: Bram Stoker
 76: George Eliot
 94: Jane Austen
 99: Austen

The cost is O(n + total pattern length + number of matches): the text is read once, whether there are 5 patterns or 5,000. The memory cost of the trie (33 nodes for 5 phrases) is as in the fourteenth post; keeping a Dictionary<char, int> in every node is expensive, and more compact implementations keep everything in a single array.

The .NET Reality: IndexOf and SearchValues<string>

I measured our algorithms against the BCL. A single word: "Middlemarch" at the end of a 100,000-character text.

| Method                | Mean         | Ratio | Allocated |
|---------------------- |-------------:|------:|----------:|
| Naive                 |    31.097 us |  1.00 |         - |
| Kmp                   |    50.851 us |  1.64 |      72 B |
| IndexOfOrdinal        |     5.867 us |  0.19 |         - |
| IndexOfCurrentCulture | 1,063.311 us | 34.19 |         - |

I ran the benchmarks one at a time, but other work was running on the machine; absolute times depend on the machine, and the column to compare is Ratio. The first surprise is that KMP is slower than naive. On normal text a mismatch almost always happens at the first character, so naive search's worst case never occurs, while KMP's failure array and extra branches add a constant cost on every character. KMP's value is in its guarantee, not its average speed. The second result: string.IndexOf(string, StringComparison.Ordinal) is 5 times faster than naive search, and the reason is not asymptotic. According to the runtime source (dotnet/runtime, SpanHelpers.Char.cs), ordinal search uses SIMD to compare the pattern's first character, and one of its last characters that differs from it, at dozens of positions at once, and does a full comparison only for candidates where both match. The source states no explicit worst-case guarantee; on pathological inputs where most candidates pass, the work grows. The last row is a separate lesson: if you do not pass a StringComparison, IndexOf(string) compares with the current culture, which is much slower.

For many words, .NET 9 brought SearchValues<string>. It accepts only Ordinal and OrdinalIgnoreCase:

SearchValues<string> sv = SearchValues.Create(banned, StringComparison.OrdinalIgnoreCase);
ReadOnlySpan<char> span = review;
Console.WriteLine($"ContainsAny: {span.ContainsAny(sv)}, first at {span.IndexOfAny(sv)}");

ContainsAny: True, first at 18

On the day of writing (2026-11-15) I looked at the StringSearchValues.cs file in dotnet/runtime. For a single value, a vectorized single-string search is selected. For several values, if the CPU supports SIMD, there are at most 80 values, the shortest value has at least 2 characters and the prefixes are ASCII, it uses the Teddy algorithm from Intel's Hyperscan library, with Rabin-Karp as a fallback for very short inputs Teddy cannot handle. In every other case the algorithm is the Aho-Corasick we wrote. So the BCL uses the same algorithm, adding a SIMD pre-scan on top where it fits. These details can change between versions; what does not change is the API's contract.

The banned-words scenario: 1,000 reviews of 500 characters each; the banned words are random 5–9 letter strings, so the reviews are clean. In real life most reviews are clean too, and this is the most expensive case, because the search never stops early.

| Method                  | BannedCount | Mean         | Ratio | Allocated |
|------------------------ |------------ |-------------:|------:|----------:|
| LoopContains            | 10          |    382.42 us |  1.00 |   88000 B |
| AhoCorasickOurs         | 10          |  2,384.73 us |  6.24 |         - |
| SearchValuesContainsAny | 10          |     52.19 us |  0.14 |         - |
|                         |             |              |       |           |
| LoopContains            | 500         | 19,550.39 us |  1.00 |   88000 B |
| AhoCorasickOurs         | 500         |  4,561.39 us |  0.23 |         - |
| SearchValuesContainsAny | 500         |  2,910.92 us |  0.15 |         - |

The answer to the opening question is in the lower half of the table. When the word list grows 50 times, the loop calling Contains per word also gets about 50 times slower. Our Aho-Corasick only gets 2 times slower; the text is still read once, and the increase comes from cache misses in a bigger trie. SearchValues is the fastest in both cases, but the difference between the two rows confirms what we read in the runtime source: with 10 words it takes 52 microseconds with Teddy, with 500 words it is past the limit of 80, switches to the Aho-Corasick inside, and takes 56 times longer. That our implementation is 6 times slower than the loop with 10 words is instructive too: stepping character by character through a Dictionary<char, int> costs more than scanning ten words with SIMD. The algorithm's complexity is right; its constant is bad.

Turkish I and Case Folding

The sample text is deliberately Turkish; I ran the same searches with ordinal and tr-TR comparison:

string text = "KİTAP KULÜBÜ: Istanbul'da bu hafta";

OrdinalIgnoreCase "kitap":    False
tr-TR IgnoreCase "kitap":     True
OrdinalIgnoreCase "istanbul": True
tr-TR IgnoreCase "istanbul":  False
SearchValues OrdinalIgnoreCase: False
tr-TR ToLower: "kitap kulübü: ıstanbul'da bu hafta" contains kitap: True

OrdinalIgnoreCase does not treat "İ" as the uppercase of "i"; that mapping exists only in the Turkish culture. The tr-TR comparison finds "KİTAP" but this time misses "Istanbul", because in Turkish the lowercase of "I" is "ı". All our algorithms compare characters one to one; they do not know language rules. The right approach is to pass both the text and the patterns through the same folding function before searching. With a function like SearchKey.Fold from the fourteenth post of this series, which reduces Turkish characters to ASCII, both "KİTAP" and "Istanbul" end up in the same form; after that, ordinal search is safe to use. You cannot do culture-sensitive search with your own KMP or with SearchValues.

In Production

Build the structure once. Building SearchValues or Aho-Corasick is expensive, searching is cheap. Build the banned-word list at application startup or when the list changes, and keep it in a singleton or a static readonly field; do not rebuild it on every request.

Check word boundaries separately. Searching for "scam" also matches "scampi". Moderation needs a second step that looks at whether there are letters on either side of the match; that is a business rule, not string search.

Put an upper limit on input. KMP and Aho-Corasick are linear, but a 10 MB review still means reading 10 MB. Limit review length in model validation.

Pattern matching needs a different tool. Rules like "a digit, then a dash, then a letter" are not fixed-string search; they are the subject of the Regular Expressions series.

Common Pitfalls

Calling IndexOf(string) without a StringComparison. It compares with the current culture: it is slower and can return different results depending on the server's culture. For technical strings (keys, codes, banned words) always write Ordinal or OrdinalIgnoreCase.

Assuming OrdinalIgnoreCase knows Turkish. In the output above, "KİTAP" was not found. Normalize Turkish content first.

Using your own KMP in production. As the measurement shows, the BCL's vectorized search is far faster in practice and well tested. Your own implementation makes sense only for a need the BCL does not cover (for example reporting which pattern matched, or searching streaming data).

Expecting SearchValues to tell you which word matched. IndexOfAny only returns the position. If you need to report which word it was, check the candidates at that position or use a structure that returns the pattern, such as Aho-Corasick's FindAll.

A Small Experiment

★☆☆ Compute Kmp.BuildFailure for "aabaaab" by hand, then verify it with the code. At which position does the value drop, and why?

★★☆ Add a word-boundary check to AhoCorasick: do not report a match if the character right before or after it is char.IsLetter. "scampi" should no longer be flagged as "scam"; pin that down with a test.

★★★ Replace the List<Dictionary<char, int>> in AhoCorasick with a single int[] transition table (nodes × 26) by limiting the alphabet to lowercase letters. Run the benchmark again: can you beat the loop with 10 words, and how much does memory grow?

In the next post we move from text to time: delivery slots, overlapping campaign dates and warehouse shifts. Sorting and merging intervals, answering "how many at most at the same time" with a sweep line, and using a monotonic structure on price history.