Released · improving
Algorithm
String algorithms find patterns in text and look up words by prefix; KMP, Rabin-Karp, tries and the Z-algorithm are the core techniques.
String algorithms are methods for comparing and searching sequences of characters quickly and correctly. The central problem is pattern matching, finding every place a short pattern occurs in a long text, but looking up all dictionary words with a given prefix and finding many patterns at once belong here too. The naive approach of checking every position can take time proportional to the text length times the pattern length.
Find-in-file, log search, search-box autocomplete, intrusion detection, file synchronization and genome analysis all run on string algorithms. KMP reuses earlier comparisons through a failure table to guarantee linear time, Rabin-Karp slides a rolling hash across the text to avoid most comparisons, and a trie shares common prefixes so that prefix lookups cost time proportional only to the word length. The topic also comes up often in coding interviews.
Start with the vocabulary of prefixes, suffixes and borders, and see by hand why naive matching is slow. Then compute a prefix-function table for a small pattern yourself, implement KMP search and a trie, and check them against the standard library. Finally, look at the pitfalls that make real-world results wrong, such as hash collisions and Unicode normalization.
Precompute the longest border of every pattern prefix; on a mismatch, fall back to a shorter border instead of rewinding the text, giving O(n + m) search.
Rabin-Karp updates the hash of each length-m window in O(1), compares it with the pattern hash and checks the characters only when the hashes match.
A tree you walk down character by character; shared prefixes are stored once, so prefix lookup and autocomplete take time proportional to the word length.
The Z-array gives, for every position, the longest common prefix with the whole string in linear time. Real text also requires care with normalization and index units.
prefix_function computes the longest border of every prefix of the pattern, and kmp_search uses that table to read the text once, left to right, collecting every start position. Because k is reset to pi[k - 1] after a match, overlapping occurrences such as those at 0 and 2 are found as well. Run python string_search.py to print both results.
string_search.py
def prefix_function(p: str) -> list[int]:
"""pi[i] = length of the longest proper border of p[:i + 1]."""
pi = [0] * len(p)
k = 0
for i in range(1, len(p)):
while k > 0 and p[i] != p[k]:
k = pi[k - 1]
if p[i] == p[k]:
k += 1
pi[i] = k
return pi
def kmp_search(text: str, pattern: str) -> list[int]:
"""Start positions of every (possibly overlapping) occurrence."""
if not pattern:
return list(range(len(text) + 1))
pi = prefix_function(pattern)
hits, k = [], 0
for i, ch in enumerate(text):
while k > 0 and ch != pattern[k]:
k = pi[k - 1]
if ch == pattern[k]:
k += 1
if k == len(pattern):
hits.append(i - k + 1)
k = pi[k - 1]
return hits
if __name__ == "__main__":
print(prefix_function("ababaca")) # [0, 0, 1, 2, 3, 0, 1]
print(kmp_search("abababcabab", "abab")) # [0, 2, 7]
python string_search.pySix chapters that take you from installation to the core ideas of String algorithms.
Ask questions, share experience and trade opinions about String algorithms.
No discussions yet. Start the first one.
0 comments
Sign in · Sign in to leave a comment.
Be the first to comment.