Lesson 46 of 50 16 minMaster

String matching: KMP and Rabin-Karp

Find every occurrence of a pattern in a text: why brute force can be O(n·m), how KMP never re-reads a letter using its failure table, how Rabin-Karp compares rolling hashes, and what .NET does for you.

Searching for a word in a document, a gene in DNA, a code in a log file, a virus signature in a file: all are string matching. The text has length n, the pattern length m. The obvious method tries every alignment and compares letter by letter. Usually it fails fast, but on unlucky inputs (text AAAA…A, pattern AAAB) every alignment almost matches, and the cost is O(n·m).

BruteForce.cs

1Console.WriteLine(string.Join(", ", FindAll("AABAACAADAABAABA", "AABA")));2 3static List<int> FindAll(string text, string pattern)4{5    var found = new List<int>();6    for (int s = 0; s + pattern.Length <= text.Length; s++)   // every alignment7    {8        int j = 0;9        while (j < pattern.Length && text[s + j] == pattern[j]) j++;10        if (j == pattern.Length) found.Add(s);11    }12    return found;13}

Output

0, 9, 12

Step through the three algorithms on the same input and compare the “letters compared” counter. Try your own text, such as AAAAAAAAAAAAAAAB with pattern AAAB, to see brute force at its worst.

KMP: never look back

When brute force hits a mismatch after matching j letters, it slides by one and re-reads letters it has already seen. But it already knows those j letters: they are the first j letters of the pattern. The Knuth-Morris-Pratt algorithm precomputes, for every prefix of the pattern, the length of its longest proper prefix that is also a suffix (the failure or LPS table). After a mismatch, the pattern slides so that this prefix lines up with the text, and comparison continues at the same text position.

Pattern	A	B	A	B	C	A	B	A	B
LPS	0	0	1	2	0	1	2	3	4

Read the table like this: after matching ABAB (LPS 2), its last two letters AB are also its first two. If the next letter fails, the pattern can slide so those two letters line up, without comparing them again.

Kmp.cs

1Console.WriteLine(string.Join(" ", BuildLps("ABABCABAB")));2Console.WriteLine(string.Join(", ", Search("ABABDABACDABABCABAB", "ABABCABAB")));3Console.WriteLine(string.Join(", ", Search("AABAACAADAABAABA", "AABA")));4 5static int[] BuildLps(string p)6{7    var lps = new int[p.Length];8    int len = 0;                                     // length of the current prefix that is also a suffix9    for (int i = 1; i < p.Length; )10    {11        if (p[i] == p[len]) lps[i++] = ++len;        // extend it12        else if (len > 0) len = lps[len - 1];        // fall back to a shorter one13        else lps[i++] = 0;14    }15    return lps;16}17 18static List<int> Search(string text, string p)19{20    var lps = BuildLps(p);21    var found = new List<int>();22    for (int i = 0, j = 0; i < text.Length; )23    {24        if (text[i] == p[j])25        {26            i++; j++;27            if (j == p.Length) { found.Add(i - j); j = lps[j - 1]; }   // keep the overlap28        }29        else if (j > 0) j = lps[j - 1];              // slide the pattern; i stays where it is30        else i++;31    }32    return found;33}

Output

0 0 1 2 0 1 2 3 4
10
0, 9, 12

The text index i only ever moves forward, and every fallback of j is paid for by an earlier step forward, so the search is O(n) and building the table is O(m): O(n + m) in total, even in the worst case.

Rabin-Karp: compare numbers, not letters

Rabin-Karp turns strings into numbers with a hash: treat the letters as digits in base B and take the result modulo a large prime M. Comparing two numbers is O(1). The trick is the rolling hash: when the window slides one place right, the new hash is computed from the old one in O(1), by removing the left letter’s contribution and adding the new right letter.

RabinKarp.cs

1Console.WriteLine(string.Join(", ", RabinKarp("AABAACAADAABAABA", "AABA")));2 3static List<int> RabinKarp(string text, string p)4{5    const long B = 256, M = 1_000_000_007;6    int m = p.Length;7    var found = new List<int>();8    if (m > text.Length) return found;9 10    long high = 1;                                   // B^(m-1) mod M: the weight of the leftmost letter11    for (int i = 1; i < m; i++) high = high * B % M;12 13    long ph = 0, wh = 0;14    for (int i = 0; i < m; i++)15    {16        ph = (ph * B + p[i]) % M;17        wh = (wh * B + text[i]) % M;18    }19 20    for (int s = 0; ; s++)21    {22        if (wh == ph && string.CompareOrdinal(text, s, p, 0, m) == 0) found.Add(s);   // same hash: check letters23        if (s + m == text.Length) break;24        wh = (wh - text[s] * high % M + M) % M;      // drop the left letter25        wh = (wh * B + text[s + m]) % M;             // bring in the right letter26    }27    return found;28}

Output

0, 9, 12

Rabin-Karp shines when searching for many patterns of the same length at once (put all pattern hashes in a hash set) and for finding repeated substrings, as plagiarism checkers and file-deduplication tools do.

In real .NET code

You rarely write these yourself. string.IndexOf, Contains and Span.IndexOf are heavily optimised with vector (SIMD) instructions and scan many characters per CPU step. One thing matters a lot, though: pass `StringComparison.Ordinal` (or OrdinalIgnoreCase) when you mean exact characters. IndexOf(string) without it uses the current culture’s rules, which is slower and can give surprising results.

Ordinal.cs

1string log = "ERR;OK;ERR;ERR;OK;ERRATA";2int count = 0;3for (int i = log.IndexOf("ERR", StringComparison.Ordinal); i >= 0;4     i = log.IndexOf("ERR", i + 1, StringComparison.Ordinal))5    count++;6Console.WriteLine(count);7Console.WriteLine(log.Contains("ok", StringComparison.OrdinalIgnoreCase));

Output

4
True

Algorithm	Time	Best for
Brute force	O(n·m) worst, fast in practice	Short patterns, everyday text
KMP	O(n + m) guaranteed	Streams (never re-reads), worst-case guarantees
Rabin-Karp	O(n + m) expected	Many patterns at once, repeated substrings
Boyer-Moore	Often less than n comparisons	Long patterns over large alphabets; skips ahead
Aho-Corasick	O(n + total pattern length + matches)	Thousands of patterns: virus scanners, word filters

Quick check

Why is KMP O(n + m) even in the worst case?

Quick check

Two windows have the same Rabin-Karp hash as the pattern. What must the algorithm do?

Practice

Use the LPS table to find the shortest repeating unit of a string: ABCABCABC → ABC, ABAB → AB, ABCAB → ABCAB (no repetition), AAAA → A.

Show a hint

Let p = n − lps[n − 1]. If n is divisible by p, the first p letters repeat to form the whole string; otherwise the string is its own unit.

Show the solution

Solution.cs

1foreach (var s in new[] { "ABCABCABC", "ABAB", "ABCAB", "AAAA" })2    Console.WriteLine($"{s}: {Unit(s)}");3 4static string Unit(string s)5{6    var lps = new int[s.Length];7    for (int i = 1, len = 0; i < s.Length; )8    {9        if (s[i] == s[len]) lps[i++] = ++len;10        else if (len > 0) len = lps[len - 1];11        else lps[i++] = 0;12    }13    int period = s.Length - lps[^1];14    return s.Length % period == 0 ? s[..period] : s;15}

Output

ABCABCABC: ABC
ABAB: AB
ABCAB: ABCAB
AAAA: A

Remember

Brute-force matching is O(n·m) in the worst case because it re-reads text after every mismatch.
KMP precomputes the longest prefix-that-is-also-a-suffix table and never moves backwards in the text: O(n + m).
Rabin-Karp compares rolling hashes in O(1) per window and confirms hash matches letter by letter.
In .NET, use IndexOf / Contains with StringComparison.Ordinal; they are vectorised and fast.

Foundations

Linear data structures

Searching and sorting

Hashing and problem-solving techniques

Trees

Graphs

Algorithm design

Master level

String matching: KMP and Rabin-Karp

Finding a pattern in text

KMP: never look back

Rabin-Karp: compare numbers, not letters

In real .NET code

Remember