Guida a Algoritmi sulle stringhe · 1/6
Per ora questo capitolo è disponibile solo in inglese.
String algorithms are techniques for working with sequences of characters quickly and correctly. Find-in-file, log search, search-box autocomplete and DNA sequence comparison all ask the same question: where does this run of characters occur? This chapter fixes the vocabulary used throughout the guide and starts from the simplest approach, naive matching, to show why better algorithms exist.
| Term | Meaning | Example (string abcab) |
|---|---|---|
| Text | The long string being searched, length n | A whole log file |
| Pattern | The short string you look for, length m | A search term |
| Prefix | A piece cut from the front | a, ab, abc |
| Suffix | A piece cut from the back | b, ab, cab |
| Border | A proper substring that is both a prefix and a suffix | ab |
| Occurrence | A position where the pattern starts in the text | A 0-based index |
| Alphabet | The set of possible characters | ASCII, ACGT for DNA |
A proper prefix is any prefix except the whole string. Borders are the heart of KMP, so it pays to get comfortable with them now.
Most string problems fall into four groups.
The obvious approach tries every starting position and compares character by character.
def naive_search(text: str, pattern: str) -> list[int]:
n, m = len(text), len(pattern)
hits = []
for start in range(n - m + 1):
j = 0
while j < m and text[start + j] == pattern[j]:
j += 1
if j == m:
hits.append(start)
return hits
print(naive_search("abracadabra", "abra")) # [0, 7]For short inputs this is fine. But with text and pattern , almost all characters match at every position before failing, so the worst case is . The real problem is that each failure throws away what the comparisons just revealed and restarts from scratch at the next position. KMP stores that knowledge in a border table and reuses it; Rabin-Karp replaces most character comparisons with a hash comparison.
aaaa...aaaa...abmO(n·m)To build intuition, compute the longest border the slow way. The next chapter computes the same values for every prefix in O(m) with the prefix function.
def longest_border(s: str) -> int:
for length in range(len(s) - 1, 0, -1):
if s[:length] == s[-length:]:
return length
return 0
for word in ["abcab", "aaaa", "abcd", "ababa"]:
print(word, longest_border(word))
# abcab 2 / aaaa 3 / abcd 0 / ababa 3The longest border of ababa is aba, of length 3. Note that the prefix and the suffix may overlap.
Python's in, str.find, str.count and the re module are already highly optimized, so you will rarely rewrite KMP just to find a substring. Knowing the algorithms still matters when:
What counts as one character is less obvious than it looks. A Python str is a sequence of code points, and one visible character may be several code points.
import unicodedata
a = "café" # single é (U+00E9)
b = "café" # e + combining acute accent (U+0301)
print(a == b, len(a), len(b)) # False 4 5
print(unicodedata.normalize("NFC", a) == unicodedata.normalize("NFC", b)) # True
print(len(a.encode("utf-8"))) # 5 (bytes)Unless text and pattern are normalized to the same form (for example NFC) before searching, words that look identical to a person will not match. The last chapter returns to this.
n, pattern length is m, and a border is a proper substring that is both a prefix and a suffix.O(n·m) in the worst case because it discards what each failed attempt learned.
0 commenti
Accedi · Accedi per lasciare un commento.