DSA · Chapter 10 of 40
String Algorithms
Beyond counting, a few named algorithms show up in interviews: naive pattern matching, KMP for linear-time search, and Rabin-Karp for rolling-hash search.
You rarely need to write KMP from memory, but you should know that pattern matching can be done in O(n + m) rather than O(n * m).
Naive matching
Try the pattern at every position: O(n * m) in the worst case, fine for short inputs.
KMP idea
Precompute the longest prefix that is also a suffix for each position, so after a mismatch you skip ahead instead of restarting.
Example 1 (python)
def naive_search(text, pat):
n, m = len(text), len(pat)
hits = []
for i in range(n - m + 1):
if text[i:i + m] == pat:
hits.append(i)
return hits
print(naive_search('abcabcab', 'abc'))Output
[0, 3]Straightforward but O(n * m).
Example 2 (python)
def build_lps(pat):
lps = [0] * len(pat)
length = 0
for i in range(1, len(pat)):
while length and pat[i] != pat[length]:
length = lps[length - 1]
if pat[i] == pat[length]:
length += 1
lps[i] = length
return lps
print(build_lps('ababaca'))Output
[0, 0, 1, 2, 3, 0, 1]The LPS table is the core of KMP.
Key points
- Naive matching is O(n * m).
- KMP achieves O(n + m) using an LPS table.
- Rabin-Karp uses a rolling hash for average-case speed.
- Know the complexities even if you cannot recall every line.
💡 Note: Say the name of the algorithm and its complexity even if you implement the simple version.