2024-09-02
This is a series on data structures and algorithms with the prefix alg as the title.
The update strategy for this series: directly update content without marking the year, month, and day of the update.
This series references many sources, an important one being the lecture notes from Tsinghua University's Data Structures course (by Deng Junhui) and the content of "Data Structures (C++ Language Edition)." Some paragraphs may have a high text copy ratio/pseudo-code copy ratio, but it is not guaranteed that the relevant parts are completely consistent with the above sources. The above materials can be accessed from this link.
Designing an algorithm is very different from proving its correctness:
The general pattern for designing an algorithm is top-down, designing an algorithm framework, and recursively implementing the functions used by the upper-level function. During the implementation of the function, it is only necessary to explain the meaning of each variable and what each step is doing in natural language.
Proving an algorithm is correct is far more complex and tedious than constructing an algorithm.
In scenarios where you need to provide in real-time code that simply works, you need to program according to the "design" pattern.
Below, we list the algorithms and proofs are not provided by default.
We want to find all occurrences of the pattern string B in the document string A. Let the length of the document string A be n, and the length of the pattern string B be m.
An intuitive idea is to align the pattern string B with the "left end" of the text string A, try to match, and if it doesn't match (referred to as a mismatch), move the pattern string a certain position to the right relative to the text string, denoted as di, and try to match again until the pattern string exceeds the right end of the text string.
Using the brute force algorithm, the pattern string moves to the right by 1 each time (di=1), resulting in a complexity of O(mn).
By utilizing the experience of already matched parts to guide the displacement di of the pattern string, the complexity of the string matching algorithm can be reduced. Under this overall scheme, the the matching at each position can be performed from left to right or from right to left, corresponding to the KMP and BM algorithms respectively.
Assume a mismatch occurs at position i in the text string, and j characters have already been matched, i.e., A[i, i+j) = B[0, j), A[i+j] != B[j]. How much should the text string move to the right? (i += di, di = ?)
The requirement is not to miss any possible matches.
di = min_{k>0} { A[i+k, i+j) == B[0, j-k) }
= min_{k>0} { B[k, j) == B[0, j-k) }
(t := j-k)
= j - max_{0<=t<j} { B[0, t) == B[j-t, j) }
:= j - next[j]
It can be seen that this displacement only relates to j and string B, which can be pre-stored in a sequence/table called the next table. For example, the next table for "MAMAMMIA" is [-1, 0, 0, 1, 2, 3, 1, 0], where next[0]=-1 ensures that when j=0 and no characters match, the pattern string moves one position to the right.
The next table can be constructed recursively:
next = [-1]*m
t = -1
j = 0
while j < m-1
if t < 0 or B[j]==B[t]
j, t = j+1, t+1
N[j] = t
else
t = next[t]
Where t is the length of the longest matching prefix and suffix of B[0, j). In other words, it is the number of characters already matched.
In each loop, the character B[j] is added. If the next character of the suffix B[j] matches the next character of the prefix B[t], then the number of matched characters increases by one. Otherwise, lower the expectation and find a shorter prefix and suffix match, which happens to be next[t].
When applying the next table for matching, after each move, it is not necessary to start matching from the left end of the pattern string again, but rather to utilize the partial results from the last time.
i, j = 0, 0
while (j < m and i < n)
if j < 0 or A[i]==B[j]
i, j = i+1, j+1
else
j = next[j]
return i-j
The loop invariant is A[i-j, i)==B[0, j). The position aligned with the left end of the pattern string is i-j.
If the next character matches, the length of the matched part increases by one, and the position aligned with the left end of the pattern string remains unchanged. Otherwise, the pattern string moves to the right by j - next[j] steps, or in other words, retains next[j] matched characters.
In the algorithm for constructing the next table, within each loop, either j and t each increase by one, or t decreases by at least one (because next[t] < t). Therefore, 2j-t increases by at least 1 in each loop, and the loop executes at most 2(m-1)-1 times, making the complexity of constructing the next table O(m).
Similarly, in the algorithm for matching the text string, 2i-j increases by at least 1 in each loop, making the complexity of matching O(m+n).
The core framework of the BM algorithm is to match from right to left, and the algorithm design is as follows:
i = 0
while n >= i + m
j = m - 1
while B[j]==A[i+j]
j = j - 1
if j < 0
break # matched
if j < 0 # matched
return i
else
i = i + max(gs[j], j - bc[A[i+j]])
Where i is the position aligned with the left end of the pattern string, and j is the position in the pattern string currently being compared (or mismatched). Each time a mismatch occurs, the distance the pattern string moves to the right is determined by the "Good Suffix" (gs) and "Bad Character" (gc) strategies, both of which can exclude a series of positions immediately following i that definitely cannot match.
If the character A[i+j] in the text string that needs to be matched appears very far to the left in the pattern string B, it may be possible to move the pattern string B significantly to the right. Based on this idea, record the rightmost position of each character c in the alphabet in B as bc[c]. Thus, for all k > bc[c], B[k] != c. It is not difficult to see that the pattern string should move to the right by at least j - bc[A[i+j]].
Since the suffix already matches B(j, m) == A(i+j, i+m), a necessary condition for the pattern to match after shifting right by s is B(j, m) == B(j-s, m-s). For each j, it is necessary to find the smallest s that satisfies the necessary condition, which is gs[j].
The construction of the gs table is quite complex and is omitted here.
With simple improvements, the complexity of this algorithm can be O(n+m).