String Matching Intuition

The Idea

Naive matching throws away everything it just learned: after four matching characters it slides the pattern one step and re-reads them all.

Precompute, for every prefix of the pattern, the longest proper prefix that is also a suffix. On a mismatch, fall back to that length — the text pointer never moves backwards.

Real-World Example

Network intrusion sensors scan packet streams for signatures at line rate and cannot rewind a stream that has already gone past. A failure table lets the matcher keep its partial progress and read every byte exactly once.

The Code

def failure(pat):
    table = [0] * len(pat)
    k = 0
    for i in range(1, len(pat)):
        while k and pat[i] != pat[k]:   # fall back to a shorter prefix
            k = table[k - 1]
        if pat[i] == pat[k]:
            k += 1
        table[i] = k                    # prefix that is also a suffix
    return table

print(failure("ababc"))   # [0, 0, 1, 2, 0]
print(failure("aaaa"))    # [0, 1, 2, 3]

def failure(pat):
  table = [0] * len(pat)
  k = 0
  for i in range(1, len(pat)):
      while k and pat[i] != pat[k]:
          k = table[k - 1]
      if pat[i] == pat[k]:
          k += 1
      table[i] = k
  return table

print(failure("abab"))