String matching¶

Every editor's search box, every grep, every call to str.find and every tool that looks for a short DNA read in a genome solves the same problem: given a text of n characters and a pattern of m, report every position where the pattern occurs. The obvious method compares the pattern at every position and can cost about n times m comparisons. This page builds four matchers from scratch and shows how each one avoids that waste: the naive matcher as the baseline, Rabin-Karp, which compares cheap rolling hashes before it compares characters, the string-matching automaton, which reads each text character exactly once, and Knuth-Morris-Pratt, which reaches the same linear time with a table of only m numbers, its prefix function. Afterwards you will be able to trace all four by hand, compute a prefix function and an automaton table, prove the linear bound of Knuth-Morris-Pratt with a potential argument, choose a modulus for Rabin-Karp, and explain what Python's own search does and when to use it instead. The page uses the counting of Asymptotic analysis, the potential method of Amortized analysis and the hashing of Hash tables; Boyer-Moore search, Tries and Suffix arrays continue from here.

The matchers need only the standard library; to run the plots and the notebook install the base group, and the sample project downloads three public-domain books on its first run.

Intuition¶

Picture looking for a word in a printed page with a strip of card that has the word written on it. You lay the strip under the start of the line, compare letter by letter, and at the first difference move the strip one letter to the right and start comparing again from the strip's first letter. That is the naive matcher, and its waste is plain to see: after matching seven letters and failing at the eighth, it moves one place and rereads letters it has just read.

Two better ideas come from everyday life. The first is a fingerprint. Instead of comparing letters, compare a number computed from the letters under the strip, such as a checksum, and look at the letters only when the numbers agree. If the number can be updated in one step as the strip moves, each position costs one cheap step. That is Rabin-Karp. The second idea is memory. Searching for GAGTGAGGA, suppose you have matched GAGTGAG and the next letter is A. The last letters read are GAGTGAGA, and without looking back you know that their final two letters, GA, are the start of the pattern. So you continue as if two letters were matched, and never reread the text. Knuth-Morris-Pratt and the string-matching automaton both work this way; they differ only in how they store what to do after each mismatch.

The diagram shows the problem at the top and the four matchers below it, each with its preprocessing and its cost, and in green the jobs each does best. Knuth-Morris-Pratt, in amber, keeps the automaton's states and replaces its table by m numbers, which makes it the classic choice when a linear bound must be guaranteed.

How it works¶

The problem and its notation¶

The text T has n characters T[0] to T[n − 1] and the pattern P has m characters P[0] to P[m − 1], both drawn from an alphabet Σ of |Σ| symbols. Indices start at 0, as in Python; books that number positions from 1 are converted where it matters. Placing the pattern under the text so that P[0] lies under T[s] is called shift s, and a shift is valid when every pattern character agrees with the text character above it:

Shift s is valid when T at s plus j equals P at j for every j from 0 to m minus 1, where s ranges from 0 to n minus m

There are n − m + 1 shifts, from 0 to n − m inclusive. The last one puts P[m − 1] under T[n − 1], and forgetting it is the most common bug in hand-written matchers. The problem is to report every valid shift, including shifts whose occurrences overlap: GAG occurs in GAGAG at shifts 0 and 2, sharing the middle G. An empty pattern occurs at every shift from 0 to n, which is also what Python reports.

The matchers below reason about prefixes of the pattern, so the first k characters get a name:

P sub k is P at 0 through P at k minus 1, for k from 0 to m; P sub 0 is the empty string epsilon

and so do the relations "is a prefix of" and "is a suffix of":

w is a prefix of x when x equals w followed by some string y; w is a suffix of x when x equals some string y followed by w

A string that is both a proper prefix and a proper suffix of x is a border of x. The empty string is a border of every nonempty string, and GAGTGAG has the borders GAG, G and the empty string. Borders are the memory of the intuition: they say how much of a match survives when the pattern moves.

w is a border of x when w is a prefix of x, w is a suffix of x, and w is shorter than x

The module notation.py writes each definition as a short, obviously correct function, is_prefix, is_suffix, borders, valid_shifts and suffix_function, and the tests use them as the oracle every fast algorithm is checked against.

The naive matcher¶

The naive matcher tries every shift from 0 to n − m. At each one it compares P[0] with T[s], P[1] with T[s + 1] and so on, and stops at the first difference; if no difference occurs, s is valid. It is correct by construction, because it applies the definition of a valid shift to every candidate. Its weakness is that nothing learned at one shift is used at the next:

Each row is one shift. At shift 1 the matcher confirms GAGTGAG and fails at T[8], and then it compares again characters it has already seen: T[8] alone is compared four times, at shifts 1, 5, 7 and 8. Eleven of the sixteen shifts fail at their first or second character, which is typical of real text; the waste is in shifts such as 5 and 7, which recheck what shift 1 already knew.

Rabin-Karp¶

Rabin-Karp turns each window of m text characters into a number and compares numbers first. Give every symbol a digit, here A = 0, C = 1, G = 2 and T = 3, and read a window as an m-digit number in base d, reduced modulo a prime q to keep it small:

t sub s is the sum over j of T at s plus j times d to the m minus 1 minus j, modulo q; p is the same sum over the pattern

The pattern's value p is computed once by Horner's rule, one multiply-add-reduce step per digit:

p equals the nested expression P at 0 times d plus P at 1, times d plus P at 2, and so on up to P at m minus 1, modulo q

The point of the method is that the next window's value follows from the current one in constant time. Moving the window one place drops the leading digit, whose weight is h = d^(m−1) mod q, shifts the remaining digits up one place by multiplying by d, and appends the entering digit:

t sub s plus 1 equals d times the quantity t sub s minus T at s times h, plus T at s plus m, modulo q, with h equal to d to the m minus 1 modulo q

So the whole text is hashed in n − m rolls after the first window. When t_s differs from p, the window cannot equal the pattern, because equal strings have equal values; no valid shift is ever skipped. When t_s equals p the window may still differ from the pattern, since many numbers share each remainder, so Rabin-Karp compares the window character by character. A hit that fails this check is a spurious hit:

The worked text with the digit of each character under it and, under the first character of each window of nine, the window's hash modulo 13: 12, 12, 1, 6, 0, 5, 11, 5, 11, 8, 10, 4, 7, 4, 5, 12; the pattern GAGTGAGGA hashes to 5, the hit at shift 5 is amber because it is spurious, and the hits at shifts 7 and 14 are green because they are valid

With the small modulus 13 used for hand tracing, three windows hash to the pattern's value 5 and one of them, at shift 5, is spurious. With a prime near a billion, the package's default, a spurious hit is rare and the verification work is essentially the cost of reporting the real matches.

Two details decide whether the method works in practice. The modulus should be a prime that shares no structure with the radix: with radix 256 and modulus 256 the hash keeps only the last character, and with the Mersenne prime 2^31 − 1 the weights repeat every 31 positions, so swapping two characters 31 places apart never changes the hash. A random radix, or a random prime, makes collisions improbable for every input, as the cost section shows. The second detail is the sign of the remainder: Python's % always returns a value in [0, q), but the % of C, Java and Go keeps the sign of the dividend, and the subtraction in the rolling update can make the dividend negative.

Rabin-Karp's real strength is many patterns at once. Patterns of the same length can share one rolling hash of the text, and a dictionary from hash values to patterns checks each window against all of them in one lookup. rabin_karp_multi does this; 199 DNA patterns of length 8 in a text of 200000 letters cost 201592 hash steps in one shared pass, against 39801592 for one pass per pattern.

The string-matching automaton¶

The automaton keeps a single number while it reads the text: how many characters of the pattern end at the current position. Formally, the suffix function σ gives the length of the longest prefix of P that is a suffix of a string x:

sigma of x is the largest k at most m such that P sub k is a suffix of x

The automaton has the states 0 to m, and its transition function says which state follows state q on reading a:

delta of q and a is sigma of P sub q followed by a, for q from 0 to m and a in the alphabet

Its invariant is that after reading T[0] to T[i] the state is σ of everything read so far, so reaching state m means the pattern ends at T[i]:

q sub i equals sigma of T at 0 through T at i; q sub i equals m exactly when shift i minus m plus 1 is valid

The induction behind it rests on one fact: if the state q is the longest prefix of P ending at T[i − 1], then the longest prefix ending at T[i] can only be an extension of a suffix of P_q, because a longer prefix ending at T[i] would, without its last character, be a longer prefix ending at T[i − 1]. So σ of the text read so far followed by a equals σ(P_q a), which is δ(q, a), and the table needs nothing but the pattern. Matching then costs exactly one table lookup per text character, whatever the text, which makes the automaton a real-time matcher: no character costs more than another.

The matching automaton of GAGTGAGGA over A, C, G and T: states 0 to 9 in a row joined by blue forward edges labelled G, A, G, T, G, A, G, G, A, state 9 double-circled in green, and orange edges below the row for the other transitions that do not return to 0: a loop on 1 labelled G, 3 to 2 on A, 3 to 1 on G, 5 to 1 on G, 7 to 4 on T, 7 to 2 on A, 8 to 1 on G and 9 to 3 on G

Every symbol without a drawn edge leads back to state 0. Building the table from the definition tries every k for every state and symbol, O(m³|Σ|) comparisons; build_automaton_naive does it that way as a reference. The prefix function of the next section gives each entry in constant time, because the row of state q, apart from its forward edge, is a copy of the row of the state that the longest border of P_q leads to:

delta of q and a is q plus 1 if q is less than m and a equals P at q; delta of 0 and a is 0 if a differs from P at 0; otherwise, for q at least 1, delta of q and a equals delta of pi at q minus 1 and a

The table has (m + 1)|Σ| cells. Symbols that do not occur in the pattern all behave alike, so a real implementation keeps one column for each pattern symbol and sends every other symbol to state 0, which is what the package does when no alphabet is given.

The prefix function¶

Knuth-Morris-Pratt keeps the automaton's states but not its table. For every position i it stores only π[i], the length of the longest border of P_(i+1), the first i + 1 characters of the pattern:

pi at i is the largest k at most i such that P sub k is a suffix of P sub i plus 1, for i from 0 to m minus 1

For GAGTGAGGA the values are 0, 0, 1, 0, 1, 2, 3, 1, 2: the prefix GAGTGAG, for example, has the longest border GAG, so π[6] = 3. The borders of a string are nested, because a border of a border is itself a border, and so the prefix function lists all of them by iteration:

The borders of P sub i plus 1 have the lengths pi at i, pi at pi at i minus 1, pi at pi at pi at i minus 1 minus 1, and so on down to 0

Following these links from every prefix of the pattern draws a tree: each prefix hangs under its longest border, and the path from any prefix up to the root lists all its borders, longest first.

The tree of failure links of GAGTGAGGA: the empty prefix 0 is the root with the children 1: G, 2: GA and 4: GAGT; 1: G has the children 3: GAG, 5: GAGTG and 8: GAGTGAGG; 2: GA has the children 6: GAGTGA and 9: GAGTGAGGA, in green; 3: GAG has the child 7: GAGTGAG; orange dashed arrows point from each prefix to its parent

The prefix 7: GAGTGAG lies three steps below the root, through 3: GAG and 1: G, so a matcher that has matched seven characters can fall back to three, then to one, then to none. The full match 9 hangs under 2: GA, the border that an overlapping occurrence can share.

Computing the table uses the same idea. A nonempty border of P_(i+1) is a border of P_i extended by the character P[i], so π[i] is one more than the longest border length k of P_i whose next character P[k] equals P[i]:

pi at i equals 1 plus the largest k in B sub i with P at k equal to P at i, for i from 1 to m minus 1, or 0 when no such k exists; B sub i is the set pi at i minus 1, pi at pi at i minus 1 minus 1, down to 0, the border lengths of P sub i

prefix_function walks the chain of B_i from the longest border down. It holds the current border length in k, compares P[k] with P[i], and on a difference falls back to π[k − 1], the next shorter border, until it finds a match or reaches 0. Trying the borders in decreasing order guarantees that the first one that extends is the longest, which is what correctness needs.

for q in range(1, m):
    while True:
        equal = pattern[k] == pattern[q]
        counter.comparisons += 1
        if equal:
            k += 1
            break
        if k == 0:
            break
        k = pi[k - 1]
    pi[q] = k

Many books number positions from 1 and index the prefix function by the length q of the matched prefix. Their table, here called π′, is the same table shifted by one:

pi prime at q equals pi at q minus 1, for q from 1 to m

So their fall-back rule "q = π[q]" becomes q = pi[q - 1] on a Python list. Copying it literally reads the border of a prefix one character too long and can loop forever; the pitfalls below show both effects.

Knuth-Morris-Pratt¶

The matcher keeps q, the number of pattern characters matched so far, and reads the text once from left to right. For each character T[i] it compares P[q] with T[i]. If they are equal, q grows by one. If not and q is positive, q falls back to π[q − 1] and the comparison is repeated with the same T[i]; if q is 0, the character is simply passed. When q reaches m, the shift i − m + 1 is valid, and q continues from π[m − 1], the longest border of the whole pattern, so that overlapping occurrences are found too. The invariant is the automaton's: before T[i] is read, q is the length of the longest prefix of P that ends at T[i − 1]. A fallback from q to π[q − 1] moves the pattern right by q − π[q − 1] places, and none of the shifts it passes over can be valid: at such a shift the pattern would start inside the q matched characters, so a prefix of P longer than π[q − 1] would also be a suffix of P_q, a border longer than the longest one.

Seven alignments replace the naive matcher's sixteen, and no text character is compared more than three times. The orange cells are the point: at shift 5 the matcher knows that GAG is already in place because it is a border of the GAGTGAG it had matched, and it compares only the next character.

Knuth-Morris-Pratt is the automaton computed on demand. Its forward edges are the automaton's spine, and each missing transition δ(q, a) is found by following failure links from q until some state k has P[k] = a. The automaton pays (m + 1)|Σ| table cells to make every character cost one step; Knuth-Morris-Pratt pays m numbers and lets a character cost several fallbacks, which, as the next section proves, average out to at most one extra comparison per character.

Cost¶

Every algorithm¶

For a text of n characters and a pattern of m:

Naive: no preprocessing and O(1) extra space. Between n − m + 1 and (n − m + 1)m comparisons, worst case Θ(nm) for m up to a constant fraction of n; on random text fewer than |Σ|/(|Σ| − 1) per shift on average.
Rabin-Karp: m hash steps of preprocessing, n hash steps to scan, and m comparisons per verified window. Expected O(n + m) plus m per valid shift when the modulus is large; worst case (n − m + 1)m comparisons when every window hits.
Automaton: Θ(m|Σ|) time and space to build the table, then exactly n transitions, O(1) in the worst case for every character.
Knuth-Morris-Pratt: at most 2(m − 1) comparisons for the prefix function and 2n for the matcher, Θ(n + m) in the worst case, with Θ(m) extra space. The bound per character is amortized: one character can cost several fallbacks, but the total cannot exceed 2n.

The distinction matters in practice. The naive bound is a worst case that real text rarely reaches. Rabin-Karp's bound is an expectation over the choice of hash and degrades only with bad luck or a bad modulus. Knuth-Morris-Pratt's linear bound holds for every input, but only for the whole text; an application that must answer within a fixed time after every character, such as a network filter, wants the automaton's per-character guarantee.

The naive matcher: best, worst and expected¶

Each shift costs at least one comparison and at most m, which gives the two bounds. The worst case is reached by a text of one repeated symbol and a pattern that differs from it only in its last character, or by a pattern that matches everywhere:

n minus m plus 1 is at most the naive comparisons, which are at most n minus m plus 1 times m; the text a to the n with the pattern a to the m minus 1 followed by b, and the text a to the n with the pattern a to the m, both cost exactly n minus m plus 1 times m

On a text of independent, uniformly random symbols the j-th character of a shift is compared only when the j before it matched, which happens with probability |Σ|^(−j). The expected cost of a shift is a geometric sum:

The expected comparisons of one shift are the sum over j from 0 to m minus 1 of the alphabet size to the minus j, which is 1 minus the alphabet size to the minus m over 1 minus the reciprocal of the alphabet size, less than the alphabet size over the alphabet size minus 1, which is at most 2; the expected total is n minus m plus 1 times that

So on random text the naive matcher is linear, with about 2 comparisons per shift for a binary alphabet and about 1.0385 for 27 symbols. Its bad cases are repetitive texts and patterns, which are exactly the ones DNA, logs and machine-generated data contain.

Rabin-Karp: hash steps, spurious hits and the modulus¶

Rabin-Karp's work splits into hashing and verification:

Hash steps are m plus m plus n minus m, which is n plus m; comparisons are at most m times v plus f, where v counts valid shifts and f spurious hits; when every shift hits, v plus f is n minus m plus 1 and the comparisons reach n minus m plus 1 times m in the worst case

If the hashes of windows that differ from the pattern behave like independent uniform values modulo q, each of them collides with probability 1/q:

The expected number of spurious hits is n minus m plus 1 minus v, over q; the expected work is O of n plus m, plus m v, plus m times n minus m plus 1 over q, which is O of n plus m times v plus 1 when q is at least m

The example rabin_karp_moduli.py measures that assumption on a random text of 50000 lowercase letters, for prime moduli just below 2^k and for 2^k itself, with radix 256:

Spurious hits against the modulus q from 8 to 65536 on logarithmic axes, the mean of five random patterns of length 10: for prime moduli the measured values lie on the dashed line n minus m plus 1 minus v over q, falling from about 7300 to 1; for moduli that are powers of two they stay at 1922 from 32 to 256, fall in steps to 75.4 at 8192 and stay there

Prime moduli follow the prediction: 399.2 spurious hits for q = 127 against 393.6 expected, and 1.0 for q = 65521 against 0.8. Powers of two do not. With radix 256 = 2^8, every digit except the last is multiplied by a multiple of 256, so modulo 2^k for k up to 8 the hash depends on the last character alone: q = 128 gives 1922.0 spurious hits, about one window in 26, and q = 65536 still gives 75.4, because the hash then depends only on the last two characters.

A fixed modulus can be attacked by anyone who knows it, since collisions are easy to construct. The remedy is randomness. With q prime and the radix d chosen uniformly at random, two different strings of length m collide only when d is a root of the polynomial formed by their differences, which has at most m − 1 roots:

The difference of the hashes of x and y with radix d is the sum over j of x sub j minus y sub j times d to the m minus 1 minus j, modulo q, a nonzero polynomial in d of degree at most m minus 1; so the probability over d that the hashes of different strings x and y collide is at most m minus 1 over q, for q prime and d uniform in 0 to q minus 1

For m = 9 and q = 1000000007 that is below one in 10^8 for any pair of strings, chosen by an adversary or not. The example also shows the Mersenne-prime trap: modulo 2^31 − 1, the radix 256 satisfies 256^31 mod q = 1, so two 40-letter strings that differ by a swap of positions 2 and 33 hash to the same value, 940687187, while a random radix separates them.

The automaton: table against time¶

Building the automaton takes Theta of m times the alphabet size in time and m plus 1 times the alphabet size cells; matching takes exactly n transitions

The right panel of the alphabet figure below counts the table entries for a pattern of length 8 as the alphabet grows from 2 to 64 symbols: 18 to 576, exactly 9|Σ|, while the prefix function of the same pattern needs 7 to 9 comparisons whatever the alphabet. For Unicode text, with over a million code points, a full table is out of the question; that is why implementations store only the pattern's own symbols, or use the prefix function.

Knuth-Morris-Pratt: the potential argument¶

A single text character can make Knuth-Morris-Pratt fall back many times, so counting per character gives no linear bound. The potential method does. Let the potential Φ be the state q. It starts at 0 and never goes negative. Reading a character costs c = f + 1 comparisons, where f is the number of fallbacks, the extra one being the comparison that ends the loop. Each fallback lowers q by at least one and the character raises it by at most one, so the potential drops by at least f − 1:

Phi sub t is q after t characters, Phi sub 0 is 0, and Phi sub t is at least 0; c sub t equals f sub t plus 1, and Phi sub t minus Phi sub t minus 1 is at most 1 minus f sub t; so the amortized cost c hat sub t, equal to c sub t plus Phi sub t minus Phi sub t minus 1, is at most 2

The reset after a full match lowers q too and costs no comparison, which only helps. Summing over the text, the potential terms telescope:

The sum of c sub t over t from 1 to n equals the sum of the amortized costs minus Phi sub n plus Phi sub 0, which is at most 2n minus q sub n

So the matcher makes at most 2n − q comparisons, where q is its final state, and the number of comparisons is exactly n plus the number of fallbacks. The prefix function is the same loop run on the pattern against itself, with k as the potential, over m − 1 positions:

The comparisons of the prefix function are m minus 1 plus the sum of its fallbacks, at most 2 times m minus 1 minus pi at m minus 1

and together:

The comparisons of Knuth-Morris-Pratt are at most 2n plus 2 times m minus 1, which is Theta of n plus m

The example kmp_amortized.py makes the potential visible. Its pattern is the Fibonacci word abaababaabaababaababa of 21 letters, whose prefix of 19 letters has the nested borders 11, 6, 3 and 1, and its text repeats that prefix followed by a c, six times.

The potential is saved up while q climbs, one unit per matched character, and spent at each c, where the matcher falls back through 19, 11, 6, 3, 1 and 0 with six comparisons, from 44 comparisons to 50 at i = 39. The whole text of 120 characters costs 150 comparisons and 30 fallbacks, under the bound of 240. The longest chain at one character is the longest chain of nested borders in the pattern, and Fibonacci words have the longest possible ones: for the Fibonacci prefixes of length 8, 13, 21 and so on up to 610 the worst character costs 3, 4, 5 up to 12 fallbacks, which is log base φ of m minus about 1.33, with φ the golden ratio. That logarithmic delay is the price of the small table, and the automaton does not pay it.

Counted comparisons¶

The example matching_costs.py counts the work per text character of every matcher, with a pattern of length 8, in three settings: random DNA, the naive worst case, and a text in which every shift is valid. For the automaton the work is its table lookups, since its matching loop compares nothing; for Rabin-Karp it is the comparisons of its verifications, on top of one hash step per character. The port of CPython's default routine, explained under In practice, is included for comparison.

Per character a linear cost is a flat line. On random DNA the naive matcher needs 1.3307 comparisons per character at n = 65536, on its prediction (1 − 4^(−8))/(3/4) ≈ 1.3333 per shift, and Knuth-Morris-Pratt 1.2373. The middle panel is the naive matcher's worst case: 7.9991 comparisons per character, about m, against 2.0001 for Knuth-Morris-Pratt, which meets its bound of 2 there, because every character fails once and matches once. In the right panel every shift is valid, and Rabin-Karp must verify every window in full, so it is exactly as slow as the naive matcher while Knuth-Morris-Pratt and the automaton read each character once.

A larger alphabet makes mismatches more likely at the first character, so the naive matcher and Knuth-Morris-Pratt both approach one comparison per character: 1.0161 and 1.0166 for 64 symbols, against 1.9963 and 1.3788 for two. The port of CPython's routine is the only one that drops well below 1, to 0.1342 comparisons per character for 64 symbols, because it skips whole windows; for two symbols it needs 1.5029, more than Knuth-Morris-Pratt, which is why CPython switches to a linear algorithm for long inputs. The automaton's table, on the right, is the only cost that grows with the alphabet.

Worked example¶

Every step below is printed by examples/worked_example.py and asserted by tests/test_worked_example.py. The text is T = CGAGTGAGAGTGAGGAGTGAGGAT, with n = 24, and the pattern is P = GAGTGAGGA, with m = 9. The shifts to try are 0 to 15, and the valid ones are 7 and 14, which overlap in the two characters GA at T[14] and T[15].

Naive matcher shift by shift¶

s = 0: T[0] = C ≠ G, 1 comparison.
s = 1: GAGTGAG matches T[1] to T[7], then T[8] = A ≠ P[7] = G, 8 comparisons.
s = 2, 4, 6, 8, 10, 12 and 15: the text character is not G, 1 comparison each.
s = 3, 9 and 13: G matches, then the second character differs, 2 comparisons each.
s = 5: GAG matches, then T[8] = A ≠ P[3] = T, 4 comparisons.
s = 7: all nine characters match, 9 comparisons, a valid shift.
s = 11: GAG matches, then T[14] = G ≠ P[3] = T, 4 comparisons.
s = 14: all nine match, 9 comparisons, a valid shift.

In all, 48 comparisons. T[8] is compared at shifts 1, 5, 7 and 8, and T[5] to T[7] at shifts 1 and 5 before shift 7 compares T[7] once more.

Rabin-Karp window by window¶

With A = 0, C = 1, G = 2 and T = 3, radix d = 4 and modulus q = 13, the pattern's digits are 2, 0, 2, 3, 2, 0, 2, 2, 0. Horner's rule reduces after every step and passes through 2, 8, 8, 9, 12, 9, 12, 11 and ends at p = 5; the first window, CGAGTGAGA, passes through 1, 6, 11, 7, 5, 9, 10, 3 and ends at t_0 = 12. The leading weight is h = 4^8 mod 13 = 3.

Rolling from shift 0 to shift 1 drops C (digit 1) and appends T[9] = G (digit 2): t_1 = (4 (12 − 1 · 3) + 2) mod 13 = 38 mod 13 = 12.
The window hashes of shifts 0 to 15 are 12, 12, 1, 6, 0, 5, 11, 5, 11, 8, 10, 4, 7, 4, 5 and 12.
Shift 5 hits with t = 5. Its window GAGAGTGAG agrees with GAG and differs at T[8] = A ≠ T: a spurious hit, 4 comparisons.
Shifts 7 and 14 hit and verify in 9 comparisons each.

That is 33 hash steps (9 for the pattern, 9 for the first window and 15 rolls), 3 verifications of which 1 spurious, and 22 comparisons.

The automaton¶

Over the alphabet A, C, G, T, the rows of the transition table are:

state 0: A to 0, C to 0, G to 1, T to 0.
state 1: A to 2, G to 1, C and T to 0.
state 2: G to 3, all others to 0.
state 3: A to 2, G to 1, T to 4, C to 0.
state 4: G to 5, all others to 0.
state 5: A to 6, G to 1, C and T to 0.
state 6: G to 7, all others to 0.
state 7: A to 2, G to 8, T to 4, C to 0.
state 8: A to 9, G to 1, C and T to 0.
state 9: G to 3, all others to 0.

Row 7 is the interesting one. After GAGTGAG, a G continues the pattern; an A leaves GAGTGAGA, whose longest suffix that starts the pattern is GA, state 2; a T leaves GAGTGAGT, ending in GAGT, state 4. Reading the text, the states after each character are 0, 1, 2, 3, 4, 5, 6, 7, 2, 3, 4, 5, 6, 7, 8, 9, 3, 4, 5, 6, 7, 8, 9, 0: state 9 is reached after T[15] and T[22], the ends of the two occurrences, in exactly 24 transitions.

The prefix function step by step¶

π[0] = 0 by definition, and k starts at 0.

i = 1: P[1] = A ≠ P[0] = G, so π[1] = 0.
i = 2: P[2] = G = P[0], so k = 1 and π[2] = 1.
i = 3: P[3] = T ≠ P[1] = A; fall back to k = π[0] = 0; T ≠ P[0] = G, so π[3] = 0.
i = 4: G = P[0], so π[4] = 1.
i = 5: A = P[1], so π[5] = 2.
i = 6: G = P[2], so π[6] = 3.
i = 7: P[7] = G ≠ P[3] = T; fall back to k = π[2] = 1; G ≠ P[1] = A; fall back to k = π[0] = 0; G = P[0], so π[7] = 1.
i = 8: A = P[1], so π[8] = 2.

The table is π = 0, 0, 1, 0, 1, 2, 3, 1, 2, after 11 comparisons and 3 fallbacks, within the bound 2(9 − 1) − 2 = 14. Position 7 is the one that walks the chain 3, 1, 0 of the border tree.

Knuth-Morris-Pratt character by character¶

T[0] = C: P[0] = G differs and q stays 0, 1 comparison.
T[1] to T[7]: GAGTGAG match one by one, q climbs from 0 to 7, 1 comparison each.
T[8] = A: P[7] = G differs, fall back to q = π[6] = 3; P[3] = T differs, fall back to q = π[2] = 1; P[1] = A matches, q = 2. Three comparisons.
T[9] to T[15]: GTGAGGA match, q climbs from 2 to 9. At q = 9 the shift 15 − 9 + 1 = 7 is valid, and q continues from π[8] = 2.
T[16] to T[22]: GTGAGGA match again from q = 2 to 9, the shift 22 − 9 + 1 = 14 is valid, and q continues from 2.
T[23] = T: P[2] = G differs, fall back to q = π[1] = 0; P[0] = G differs, 2 comparisons.

The matcher makes 27 comparisons and 3 fallbacks, 24 characters plus 3, within the bound 2n = 48, and finds 7 and 14. The states it passes through are the automaton's, and the alignment figure in How it works shows the same run as seven alignments.

Side by side¶

On this input the naive matcher makes 48 comparisons, Rabin-Karp 22 comparisons and 33 hash steps, the automaton 24 transitions after building 40 table cells, and Knuth-Morris-Pratt 27 comparisons after 11 for its prefix function. On a text this short the differences are small; the cost section shows how they grow.

The code¶

The package string_matching is plain Python, one idea per module. Importing it needs only the standard library; Matplotlib is imported by plotting.py alone. Every matcher works on any sequence whose items can be compared with ==, so lists of words or bytes objects work as well as strings.

notation.py holds the definitions as slow, obviously correct functions: is_prefix, is_suffix, borders, longest_border, valid_shifts, suffix_function and the conversion to one-based tables.
counting.py holds OperationCounter, whose fields are comparisons, fallbacks, hash steps, verifications, spurious hits, transitions, table entries and filter checks, and CountedKey, a wrapper that counts equality tests from outside a function.
trace.py holds the Step record, record, describe, format_trace and format_alignment, which turn a search into the lines printed above.
naive.py, rabin_karp.py, automaton.py, prefix_function.py and kmp.py hold the four matchers and the prefix function; rolling_hash.py holds Horner's rule and the rolling update, and multi_pattern.py the shared pass for many patterns.
matchers.py puts the four matchers behind one search(text, pattern, algorithm) function.
analysis.py holds the closed forms of the cost section, which tests and plots compare with the counts.
cpython_search.py holds the port of CPython's default search routine and its rule for choosing a routine; comparisons.py holds Python's own search: the str.find loop for overlapping matches, str.count, the in operator and re.
invariants.py holds prefix_function_violation, automaton_violation, shifts_violation and states_violation, each with is_ and check_ forms, which the tests run on thousands of random inputs.
workloads.py holds the worked example and seeded inputs: random texts, planted occurrences, the adversarial inputs and Fibonacci words.
drawing.py, hash_drawing.py and automaton_drawing.py return deterministic Graphviz text for alignments, rolling hashes, the automaton and the border tree; pitfalls.py holds the deliberately broken versions below; plotting.py draws every figure in the handbook's colours.

Counting and tracing never change what the code does. The heart of the Knuth-Morris-Pratt matcher is this loop:

for i, symbol in enumerate(text):
    while True:
        equal = pattern[q] == symbol
        counter.comparisons += 1
        if equal:
            q += 1
            break
        if q == 0:
            break
        q = pi[q - 1]
        counter.fallbacks += 1
    if q == m:
        shifts.append(i - m + 1)
        q = pi[m - 1]

The examples run in a few seconds each from the repository root:

examples/worked_example.py prints every step of the worked example and writes the five generated diagram sources.
examples/matching_costs.py counts every matcher over text lengths and alphabet sizes.
examples/rabin_karp_moduli.py measures spurious hits against the modulus, shows a structured collision and runs many patterns in one pass.
examples/kmp_amortized.py draws the potential argument and measures the longest fallback chains.
examples/common_mistakes.py runs every broken version from pitfalls.py next to the correct code.
examples/compare_with_builtins.py checks the package against str.find, str.count and re, and times them roughly.
examples/practice.py prints fresh exercises with their solutions; --seed gives a new set.

python strings/string-matching/examples/worked_example.py
python strings/string-matching/examples/matching_costs.py
python strings/string-matching/examples/rabin_karp_moduli.py
python strings/string-matching/examples/kmp_amortized.py
python strings/string-matching/examples/common_mistakes.py
python strings/string-matching/examples/compare_with_builtins.py
python strings/string-matching/examples/practice.py --seed 7

The sample project, project/book_search.py with its helpers project/corpus.py and project/searching.py, is a small grep for books. On its first run it downloads three public-domain books from Project Gutenberg into .data/string-matching at the repository root and checks each file against a pinned SHA-256 checksum: Alice's Adventures in Wonderland, Frankenstein and The Adventures of Sherlock Holmes, 1120625 characters once the licence text is stripped and runs of whitespace are collapsed, so that a phrase still matches across a line break. It then searches them for eight patterns with every algorithm, prints the first matches of each book in context, reports the work each algorithm counted over all three books, checks every list of shifts against the str.find loop and every count against str.count, runs all patterns in one Rabin-Karp pass per length, and measures the comparisons per character for patterns of 2 to 32 characters taken from Frankenstein. Options choose the patterns, the books, the algorithms, case folding, the context width and the sweep; the default run takes about half a minute.

python strings/string-matching/project/book_search.py
python strings/string-matching/project/book_search.py "Mock Turtle" "Hatter" --books 11 --ignore-case

On English prose the naive matcher is nearly linear: 1.0015 comparisons per character for Watson, because most text characters already differ from the pattern's first letter, and 1.0895 for the, whose first letter is common. Knuth-Morris-Pratt saves only a little on such text, 1.0011 and 1.0554. Rabin-Karp verifies 0.0004 comparisons per character for Watson on top of its one hash step per character. The port of CPython's routine needs 0.1972 comparisons per character for Holmes and 0.3738 for the, since it skips most windows without comparing them. Searching for Victor also finds Victoria, a reminder that matchers find substrings, not words. The eight patterns have six distinct lengths, so the shared Rabin-Karp pass needs 6723930 hash steps against 8965180 for one pass per pattern.

Comparisons per text character in Frankenstein against the pattern length from 2 to 32, the mean of three patterns taken from the book: naive between 1.04 and 1.13 and Knuth-Morris-Pratt just below it, a dashed line at 1 for the automaton's one transition per character, the port of str.find falling from 0.40 at length 2 to 0.11 at length 32, and Rabin-Karp's verifications near 0

The longer the pattern, the further CPython's routine jumps after a failed window, from 0.3989 comparisons per character for two-character patterns to 0.1103 for 32. The other matchers stay near one per character whatever the length: they must look at every character, the skipping matchers need not, which is the subject of Boyer-Moore search.

The notebook string_matching.ipynb follows this page: the definitions, the four matchers on the worked example with their traces and diagrams, the invariants on random inputs, the counted costs, the comparison with str.find and the project's search on one book. The tests in tests check the worked example value by value, every matcher against the definition and against str.find on random inputs, the invariants of the prefix function, the automaton and the matcher states, and the cost bounds on counts, and run in a few seconds:

python -m pytest strings/string-matching

The books are public domain in the United States and are distributed by Project Gutenberg under the Project Gutenberg License, which allows copying and redistribution; they are downloaded at run time and never committed. All other data are synthetic, generated from seeds by workloads.py.

In practice¶

Python's str.find, str.count and in¶

Python's string methods are written in C and are the right choice for searching one string in another. text.find(pattern) returns the first valid shift or −1, text.find(pattern, start) the first one from start on, and pattern in text answers whether there is one. A loop of find calls restarting one place after each match returns every valid shift, and examples/compare_with_builtins.py shows that the four matchers agree with it on 800 random inputs:

from string_matching import find_all_builtin, search

text, pattern = "CGAGTGAGAGTGAGGAGTGAGGAT", "GAGTGAGGA"
assert find_all_builtin(text, pattern) == search(text, pattern, "kmp") == [7, 14]
assert text.count(pattern) == 1

The last line is the catch. str.count, like str.replace, str.split and re.finditer, counts occurrences that do not overlap: after a match it continues after the end of the match. The worked example has two valid shifts but count returns 1, and GAGAGAGAG contains GAGAG three times while count says once. When overlaps matter, use the find loop, or a regular expression with a lookahead, (?=GAGAG), which matches the empty string in front of each occurrence without consuming it.

What CPython actually runs¶

CPython's search, in Objects/stringlib/fastsearch.h, is neither the naive matcher nor Knuth-Morris-Pratt. For short texts and patterns, which means a text under 2500 characters, a pattern under 6, or a pattern under 100 in a text under 30000, it runs a routine that mixes Boyer-Moore-Horspool with Sunday's trick. It compares the last pattern character first and, after a failed window, looks at the text character just past the window: if a filter of one machine word, one bit per character code modulo 64 on most platforms, says that character does not occur in the pattern, no window containing it can match and the search jumps m + 1 places. One-character patterns get a plain scan, done by memchr for longer texts. For longer inputs CPython 3.10 and later run the two-way algorithm of Crochemore and Perrin, which is linear in the worst case and needs only constant extra space, and when the pattern is a large share of the text an adaptive version starts with the fast routine and switches to two-way after too many partial matches. The rule is reproduced by cpython_strategy, and cpython_find and cpython_count port the short-input routine with its comparisons counted, agreeing with str.find and str.count on every test input. The figures above show why it is the default: on English text it compares far fewer characters than any matcher on this page, because it skips. Its worst case on its own is quadratic, which is what the switch to two-way prevents. How skipping works, and why longer patterns search faster, is the subject of Boyer-Moore search.

In wall-clock time the gap is larger still: finding every occurrence of a 12-letter pattern in 300000 random letters took the str.find loop about a tenth of a millisecond and kmp_search close to a tenth of a second, several hundred times slower, the usual distance between C and Python made larger by the skips.

Regular expressions¶

The re module searches for patterns with alternatives, classes and repetition by backtracking over a compiled program. For a literal pattern it is slower than str.find and gives the same answer; re.escape makes a string literal, so that a dot or a star in the pattern is not read as syntax. For several literal patterns at once an alternation the|theme|thesis finds them in one pass, but each position is tried against the alternatives in order and matches are non-overlapping, so the longer alternatives must come first. Engines built on automata, such as RE2, Rust's regex crate and grep, compile a pattern into a finite automaton like the one on this page and guarantee time linear in the text.

Elsewhere¶

When to use which:

Use str.find, in, str.count or the find loop for a single pattern in Python; write your own matcher only to learn, to count work, or for sequences that are not strings.
Use Knuth-Morris-Pratt when the text is a stream read once, when a worst-case linear bound matters, or when the borders themselves are the question: the prefix function also gives the period of a string, m − π[m − 1], and answers whether a string is a rotation of another.
Use the automaton when every character must cost the same constant time and the alphabet is small, as in network intrusion detection and hardware matchers.
Use Rabin-Karp for many patterns of one length, for finding repeated substrings and for fingerprints of documents: plagiarism detection and data deduplication compare rolling hashes of windows, and the rsync tool finds unchanged blocks with a rolling checksum.
Use Aho-Corasick, the automaton generalised to a set of patterns over a trie, for many patterns of any length, as in Tries; and use a suffix array or an index when the same text is searched many times, as in Suffix arrays.

The C library's strstr uses the two-way algorithm in musl and, for long patterns, in glibc; C++17 offers std::boyer_moore_searcher and std::boyer_moore_horspool_searcher; Java's String.indexOf is a naive loop made fast by intrinsics; Go's strings.Index uses Rabin-Karp for some inputs and a vectorised scan for short patterns. Tools such as grep and ripgrep combine skipping searches with vector instructions that test many bytes at once.

Pitfalls¶

Stopping one shift short. The shifts run from 0 to n − m inclusive; range(n - m) misses an occurrence at the very end, so TACG is found in TACGGTACG at 0 but not at 5. examples/common_mistakes.py runs this and every following mistake.
Writing if where while belongs in the prefix function. One fallback is not always enough: with a single fallback the table of CTCTCA ends in 1 instead of 0, claiming a border that does not exist. Trace the full chain k, π[k − 1], π[π[k − 1] − 1] until a character matches or k reaches 0.
Restarting from 0 instead of falling back. A prefix function that resets k to 0 or 1 on a mismatch forgets shorter borders: for AACAAAC it gives 0, 1, 0, 1, 2, 1, 0 instead of 0, 1, 0, 1, 2, 2, 3.
Mixing one-based and zero-based tables. The rule q = π[q] from a book that numbers from 1 is q = pi[q - 1] on a Python list. Copied literally, it misses CTCTCA in GCTCTCTCAG, and for CCC it never terminates, because pi[2] = 2 does not decrease q. When tracing by hand, write the index next to every π value and say which convention the table uses.
Restarting from q = 0 after a full match. The next occurrence may overlap the one just found; continuing from π[m − 1] finds it, restarting from 0 misses the occurrence at shift 14 of the worked example.
Trusting equal hashes. Without verification Rabin-Karp reports spurious hits as matches: shift 5 of the worked example. Every hit must be compared character by character.
Choosing a modulus that keeps only part of the window. A power of two with radix 256 hashes only the last few characters, and a modulus in which the radix has a small order, such as 2^31 − 1 for radix 256, makes positions 31 apart interchangeable. Use a large prime and, against adversarial input, a random radix.
Taking the remainder in a language where it can be negative. In C, Java and Go, % keeps the sign of the dividend, so the rolling update can produce a negative value that never equals the pattern's hash: with that remainder the worked example finds no match at all. Add q before reducing, or reduce twice.
Counting overlapping occurrences with str.count. It counts non-overlapping ones, as do re.finditer, str.replace and a find loop that restarts after the end of each match. GAGAG occurs in GAGAGAGAG at 0, 2 and 4, but count returns 1.
Expecting a matcher to find words. Searching for Victor also finds Victoria; search for word boundaries with a regular expression such as \bVictor\b when words are meant.
Forgetting the alphabet in the automaton's cost. A table over every Unicode code point has more than a million columns; store only the pattern's symbols and send the rest to state 0.
Believing every character costs O(1) in Knuth-Morris-Pratt. The bound is amortized; one character can cost about log base φ of m fallbacks. Use the automaton when every single character must be fast.