AlgoVerse

String matching with a finite automaton

Build a finite automaton for the pattern whose state is how much of the pattern has matched so far; then read the text with one table look-up per character.

Build a finite automaton whose state q means "the first q characters of the pattern have matched so far". On each text character the automaton moves to the next state with one look-up in the table δ; reaching state m means the pattern is found.

Read the full explanation ↓
Input:
T="abababacaba" · P="ababaca"PDF export

The pattern ababaca and the text abababacaba; the automaton has 8 states and the pattern occurs at shift 2.

  1. def automaton_match(T, P):
  2. m = len(P)
  3. sigma = sorted(set(P) | set(T)) # the alphabet, in the order of delta's columns
  4. # delta[q][a]: the state after reading a in state q = the longest prefix of P that ends P[:q] + a.
  5. delta = [[0] * len(sigma) for _ in range(m + 1)]
  6. for q in range(m + 1):
  7. for j, a in enumerate(sigma):
  8. k = min(m, q + 1)
  9. while not (P[:q] + a).endswith(P[:k]):
  10. k = k - 1
  11. delta[q][j] = k
  12. q = 0
  13. shift = 0 # where P sits under T, for the picture
  14. matches = []
  15. for i in range(len(T)):
  16. q = delta[q][sigma.index(T[i])]
  17. shift = i - q + 1
  18. if q == m:
  19. matches.append(i - m + 1)
  20. return matches

Invariant: After reading T[0..i], the state q is the length of the longest prefix of P that ends T[0..i].

Start

012345678910
abababacaba
ababaca
sigma—
matches—

The table is still empty.

Local variables

T'abababacaba'
P'ababaca'

Orange = changed in this step

Call stack

  1. automaton_match()line 1
Step 1 of 301
Black = read · Orange = key steptransition: 0/24 · read: 0/11 · found: 0/1
    Explanation

    The idea

    Build a finite automaton whose state q means "the first q characters of the pattern have matched so far". On each text character the automaton moves to the next state with one look-up in the table δ; reaching state m means the pattern is found.

    Building δ

    δ(q, a) is the length of the longest prefix of P that is a suffix of P[:q] + a: q + 1 if a is the pattern's next character, otherwise a smaller state that is still valid. Here it is built the simple textbook way; with KMP's prefix function it can be built in O(m·|Σ|).

    Comparison

    Reading the text is exactly one step per character (O(n)), even simpler than KMP; but the table grows large for big alphabets. KMP is really this automaton keeping only π and computing transitions on the fly.

    What to watch in the trace

    • The delta table: each row is a state and each column a character, in the order of the sigma card.