String Algorithms

Substring Search & Hashing

Find patterns efficiently with rolling hashes or prefix functions (KMP).

Hard, optional depth, about 100 minutes to practise.

1Understand

The idea

Comparing the pattern at every position is O(n·m). KMP precomputes, for each prefix of the pattern, its longest proper prefix that is also a suffix, so after a mismatch it never re-reads text it has already matched (O(n + m)). Rolling hashes compare a window in O(1) by updating its hash as it slides.

Intuition

Comparing the pattern at every text position naively is O(n·m). KMP precomputes, for each prefix of the pattern, the longest proper prefix that is also a suffix, so after a mismatch you never re-read text you already matched, O(n + m).

Rolling hashes compare a window in O(1) after O(1) updates as the window slides; verify collisions if the problem demands certainty.

Reach for KMP or Rabin-Karp when n·m is too large under the constraints.

What you will be able to do

  • Roll a hash in O(1)
  • Verify matches to avoid false positives

When to use it

  • Find a pattern in a long text
  • Repeated substrings of length k
  • Shortest palindrome / period of a string

2See it

Walkthrough

KMP scan with LPS

text = ababc, pattern = abc, j falls back on mismatch without rescanning text.

1 / 4

iL
a
b
a
b
c
01234
i → index 0L → index 0

LPS for "abc" is [0,0,0]. i scans text, j scans pattern. Both start at 0.

j = 0 # pattern index

Live template

Line 1 active

1h = 0
2for i, ch in enumerate(text):
3 h = (h * B + ord(ch)) % M
4 if i >= k: h = (h - ord(text[i - k]) * B**k) % M

Complexity: time O(n + m), space O(m)

KMP O(n + m) time and O(m) space for π. Naive O(n·m). Rabin-Karp expected O(n + m) with good hashing; worst case degrades if you do not verify. Prefer naive when m is tiny.

Read the walkthrough as text

KMP idea on text `ababc`, pattern `abc`.

  1. LPS (π) for abc is [0,0,0], no proper prefix equals a suffix until repeats exist (e.g. abab → [0,0,1,2]).
  2. Scan text with pointer i, pattern with j. Match a,b; at text a vs pattern c, mismatch.
  3. j falls back via π (here to 0); continue. Eventually match abc at index 2.
  4. Total comparisons stay linear.

Rolling hash: hash of s[i:i+m] updates by removing s[i] and adding s[i+m] with powers of a base mod a prime.

3Recognise it

Kinds of problems (5)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Rabin-Karp rolling hash

    Example. Find pattern p in text t in expected O(n).

    How. Roll hash over length-m windows; verify equality on hash match.

  • KMP prefix function

    Example. Linear substring search with prefix table.

    How. Build pi on pattern; on mismatch fall back j = pi[j-1].

  • Repeated substring pattern

    Example. Is s built from repeating a smaller string?

    How. KMP: full string matches prefix function at end (n - pi[n-1] divides n).

  • Longest duplicate substring (hash + binary search)

    Example. Longest repeated substring in s.

    How. Binary search length L; Rabin-Karp check if any hash repeats.

  • Shortest palindrome

    Example. Add chars to front to make palindrome.

    How. Find longest prefix that is suffix-palindrome via KMP on s + # + reverse(s).

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Hash collision ignored

    Why it happens. Equal hash means equal string with high probability.

    How it fails. Hash collision on "abc" vs "xyz" returns true without char compare, wrong index.

    Fix. On hash match: verify pattern == text[i:i+m].

  • Slicing each step

    Why it happens. Slice compare is the obvious Rabin-Karp check every step.

    How it fails. O(n) slice per window → O(n·m) defeats rolling hash purpose.

    Fix. Roll hash in O(1); slice only on hash hit.

  • Power recomputed

    Why it happens. B**k each step is only one exponentiation.

    How it fails. Recompute pow(B,k) or B**k inside the loop, extra log factor per window.

    Fix. Precompute B^(k-1) mod M once; update remove term with stored power.

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons