String matching — naive, hashed, and 'just use in'
String matching
Finding a pattern in a string. You almost never need to write this — pat in text and text.find(pat) call into tuned C. But understanding underneath gives vocabulary for exotic cases (multi-pattern search, plagiarism, substring frequency).
Naive scan — O(n × m)
Slide pattern along text, compare char-by-char. Worst case "aaaa...aab" with pattern "aab": match m-1 chars before failing. In practice, random text mismatches fast so naive is close to O(n).
Rabin-Karp — O(n + m) expected
Hash substrings. Slide a rolling hash: subtract leaving char, add new one. If hashes match, verify with full compare.
Two knobs: base (prime larger than alphabet, e.g. 257) and modulus (large prime like 2^61 - 1).
Rabin-Karp shines for many patterns same length — hash them into a set, roll text hash, check membership.
When to reach for regex
re.search for structured patterns (\d{3}-\d{4}). Never for literals — in is faster and no escaping. Beware catastrophic backtracking: (a+)+b on "aaaaaX" is exponential.
Common pitfalls
- Rolling hash without verification. Different strings can share hash. Always
==verify. - Using regex for literals.
re.search("foo.bar", s)matches "foo bar" too..is any char.
Try it
- Extend
rabin_karpto return every match position. Test on"abababab"searching"aba". - Given 100 patterns of length 8 in a 1 MB text, sketch which algorithm and why. Hint: one hash pass, set membership per window.
3 graded exercises
Write the code, click Check. We’ll tell you exactly what to fix.
- Exercise 1
Write
find_all(text, pattern)that returns a list of every starting index wherepatternappears intext. Overlapping matches count. Return [] ifpatternis empty or not found. - Exercise 2
Write
is_anagram(a, b)that returns True if stringsaandbare anagrams (same characters with the same frequencies), else False. Comparison is case-sensitive. - Exercise 3
Write
longest_common_prefix(strs)that returns the longest string that is a prefix of every string in the liststrs. Return '' if there's no common prefix or the list is empty.