String Matching

You flip a coin all afternoon and write down every result: HHTHHTHHH. A friend bets that the run HHTHHH will show up somewhere. Did it, and where?

That is string matching: find every place a short pattern of length m appears in a long text of length n. Your editor's Find box does it, and so does a genome search. Those texts get huge, so the method matters.

#The naive way: try every start

Line the pattern up under the text at position 0 and compare character by character. On the first mismatch, slide the pattern one step right and start again from its first character.

for start from 0 to n - m:  k = 0  while k < m and text[start + k] == p[k]:    k = k + 1  if k == m: record start

Each of about n starts can cost up to m comparisons: O(n·m). Search a million Hs for HHHHHHHHHT and every start matches nine characters before failing.

function naiveSearch(text, pattern) {
  if (pattern.length === 0) return [];
  const found = [];
  for (let start = 0; start + pattern.length <= text.length; start++) {
    let k = 0;
    while (k < pattern.length && text[start + k] === pattern[k]) k++;
    if (k === pattern.length) found.push(start);
  }
  return found;
}
 
naiveSearch("HHTHHTHHH", "HHTHHH"); // [3]

def naive_search(text, pattern):
    if not pattern:
        return []
    found = []
    for start in range(len(text) - len(pattern) + 1):
        k = 0
        while k < len(pattern) and text[start + k] == pattern[k]:
            k += 1
        if k == len(pattern):
            found.append(start)
    return found
 
naive_search("HHTHHTHHH", "HHTHHH")  # [3]

#KMP: never read a character twice

Look at the first step again. When the mismatch happened, we had just matched HHTHH. We know exactly what those five text characters are, because they equal the start of the pattern. Throwing that knowledge away and re-reading them is the waste.

The Knuth-Morris-Pratt algorithm (KMP) keeps it. The matched part HHTHH ends with HH, and the pattern also starts with HH. So slide the pattern until its first HH sits under those last two text characters. They already match, so carry on comparing from pattern position 2. The text pointer never moves backwards.

A piece that is both a prefix and a suffix of a string (but not the whole string) is a border. HHTHH has borders H and HH. Use the longest border: it gives the smallest slide, so no real match is skipped.

The borders depend only on the pattern, never on the text. So KMP works them out once, before searching, and stores them in the failure table: table[i] is the length of the longest border of pattern[0..i].

#Building the failure table

k is the length of the border found so far. At each new character, try to extend that border by one. If it does not fit, fall back to the border of the border, table[k − 1], and try again.

table[0] = 0, k = 0for i from 1 to m - 1:  while k > 0 and p[i] != p[k]:    k = table[k - 1]  if p[i] == p[k]: k = k + 1  table[i] = k

#Searching with the table

The search loop has the same shape. j counts how many pattern characters currently match. On a mismatch, j drops to table[j − 1] while i, the text position, stays put.

j = 0for i from 0 to n - 1:  while j > 0 and text[i] != p[j]:    j = table[j - 1]  if text[i] == p[j]: j = j + 1  if j == m: record i - m + 1

function buildTable(pattern) {
  const table = new Array(pattern.length).fill(0);
  let k = 0; // length of the current border
  for (let i = 1; i < pattern.length; i++) {
    while (k > 0 && pattern[i] !== pattern[k]) k = table[k - 1];
    if (pattern[i] === pattern[k]) k++;
    table[i] = k;
  }
  return table;
}
 
function kmpSearch(text, pattern) {
  if (pattern.length === 0) return [];
  const table = buildTable(pattern);
  const found = [];
  let j = 0; // pattern characters matched so far
  for (let i = 0; i < text.length; i++) {
    while (j > 0 && text[i] !== pattern[j]) j = table[j - 1];
    if (text[i] === pattern[j]) j++;
    if (j === pattern.length) {
      found.push(i - j + 1);
      j = table[j - 1]; // keep going: matches can overlap
    }
  }
  return found;
}

def build_table(pattern):
    table = [0] * len(pattern)
    k = 0  # length of the current border
    for i in range(1, len(pattern)):
        while k > 0 and pattern[i] != pattern[k]:
            k = table[k - 1]
        if pattern[i] == pattern[k]:
            k += 1
        table[i] = k
    return table
 
def kmp_search(text, pattern):
    if not pattern:
        return []
    table = build_table(pattern)
    found = []
    j = 0  # pattern characters matched so far
    for i, ch in enumerate(text):
        while j > 0 and ch != pattern[j]:
            j = table[j - 1]
        if ch == pattern[j]:
            j += 1
        if j == len(pattern):
            found.append(i - j + 1)
            j = table[j - 1]  # keep going: matches can overlap
    return found

The inner while looks like it could make this O(n·m). It cannot. j rises by at most 1 per text character, and every fallback lowers it. It cannot fall more often than it rose, so the whole search is at most 2n steps. The table build works the same way. It is the "count total moves" argument from two pointers.

#Rabin-Karp: compare fingerprints

A completely different idea: turn each window of m characters into a number, a hash, and compare numbers instead of strings. Two numbers are compared in one step. The trick is computing each window's number in O(1) from the previous one.

Try it with digits: search for 265 in 31415926535. The first window reads 314. To slide one step, drop the leading 3, shift left, and bring in the next digit: (314 − 3 × 100) × 10 + 1 = 141. That is a rolling hash.

target = value(p), h = value(text[0..m-1])for start from 0 to n - m:  if h == target and window == p: record start  h = (h - text[start] * 100) * 10 + text[start + m]

Real text works the same way: treat each character code as a digit in base 256. Those numbers get huge, so keep every value modulo a large prime such as 1,000,000,007.

The modulo has a price: different windows can share a hash. With modulo 7, 314 and 265 both leave remainder 6. So a hash match only means "maybe". Always confirm by comparing the actual characters. When hashes differ, the strings are certainly different, and that is where the speed comes from.

function rabinKarp(text, pattern) {
  const n = text.length, m = pattern.length;
  const BASE = 256, MOD = 1_000_000_007;
  if (m === 0 || m > n) return [];
  let high = 1; // BASE^(m-1) % MOD: the weight of the leading character
  for (let i = 0; i < m - 1; i++) high = (high * BASE) % MOD;
  let target = 0, h = 0;
  for (let i = 0; i < m; i++) {
    target = (target * BASE + pattern.charCodeAt(i)) % MOD;
    h = (h * BASE + text.charCodeAt(i)) % MOD;
  }
  const found = [];
  for (let start = 0; start + m <= n; start++) {
    if (h === target && text.slice(start, start + m) === pattern) found.push(start);
    if (start + m < n) {
      h = (h - (text.charCodeAt(start) * high) % MOD + MOD) % MOD; // drop the left char
      h = (h * BASE + text.charCodeAt(start + m)) % MOD;           // add the right char
    }
  }
  return found;
}

def rabin_karp(text, pattern):
    n, m = len(text), len(pattern)
    BASE, MOD = 256, 1_000_000_007
    if m == 0 or m > n:
        return []
    high = pow(BASE, m - 1, MOD)  # the weight of the leading character
    target = h = 0
    for i in range(m):
        target = (target * BASE + ord(pattern[i])) % MOD
        h = (h * BASE + ord(text[i])) % MOD
    found = []
    for start in range(n - m + 1):
        if h == target and text[start:start + m] == pattern:
            found.append(start)
        if start + m < n:
            h = (h - ord(text[start]) * high) % MOD   # drop the left char
            h = (h * BASE + ord(text[start + m])) % MOD  # add the right char
    return found

For a single everyday search, use your language's built-in (indexOf, str.find). Write KMP when you need a guaranteed O(n + m), or the failure table itself. Reach for Rabin-Karp when you compare many windows at once, such as finding a repeated substring of length m: put every window's hash in a hash set.

#Common mistakes

#Check yourself

#What to practise next

Build the failure table for ABCABD by hand, then check it with the code. Then move on to Segment Trees and Fenwick Trees, which answer range questions on data that keeps changing.