String Algorithms
Algorithms for searching, comparing, compressing, and processing text.
Algorithm Purpose Typical use
Naive Search Try matching at each position. Small text or simple tasks
KMP Avoid rechecking characters. Fast substring search
Trie Store words by prefixes. Autocomplete / dictionary
Important tasks
- Find a substring inside text.
- Check palindromes.
- Count character frequencies.
- Find longest common prefix.
- Match patterns using regular expressions.
Simple substring search
for i from 0 to len(text) - len(pattern):
if text[i : i+len(pattern)] == pattern:
return i
return -1
Useful techniques
- Two pointers: useful for palindromes and reversing.
- Sliding window: useful for longest substring problems.
- Hashing: compare substrings faster.
- Trie: search many words with shared prefixes.
Common mistakes
- Off-by-one errors in slices or indexes.
- Confusing characters with bytes in Unicode text.
- Using a slow nested loop when a sliding window would be better.
Practice
- Check if "level" is a palindrome.
- Find the first repeated character in a word.
- Design a trie for words: cat, car, dog.
Study tip: learn the idea first, trace one small example by hand, then code it.
Computer Algorithms Quick Guide - String Algorithms