~/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 (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 tolen(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.