progress

~/problems

Problems

Basics first, then the classics, then company-style assessments. Every problem has tests you run right here; multi-level ones unlock as you go. See the roadmap.

String matching

String matching (KMP, Z-function)

Prefix function and Z-array: find every occurrence, periods and borders in O(n).

Notes

Recognise it when: you need every occurrence of a pattern, the shortest period, borders (prefix = suffix), or a DP that tracks "how much of the pattern is matched so far".

def prefix_function(s):
    pi = [0] * len(s)
    for i in range(1, len(s)):
        k = pi[i - 1]
        while k and s[i] != s[k]:
            k = pi[k - 1]
        if s[i] == s[k]:
            k += 1
        pi[i] = k
    return pi
  • Find pattern p in t: prefix function of p + "#" + t; every value equal to len(p) ends a match.
  • Shortest period: n - pi[n-1] (it divides n exactly when the string is a repetition).
  • Automaton DP: the state is the matched length; a mismatch falls back along pi.

Gotchas: the separator must not occur in either string.

0 problems

No problems match those filters.

esc