Boyer-Moore算法强好后缀规则在短模式匹配中的应用疑问
abc (Length 3) Hey there! Let's clear up how to apply the strong good suffix rule for your Boyer-Moore implementation when working with the short pattern abc (length 3). I'll break down the preprocessing first, then walk through the full algorithm for both your target strings, counting comparisons along the way.
First: Preprocessing for abc
1. Bad Character Table
We first build the standard bad character table, which tracks the last occurrence index of each character in the pattern:
'a': 0'b': 1'c': 2- All other characters: -1
2. Strong Good Suffix Preprocessing
For short patterns like abc, the strong good suffix rule mainly affects how we move the pattern after a full match (since partial matches will rarely trigger a better move than the bad character rule). Here's how it works for abc:
- When we find a full match (the entire pattern
abc), we look for another occurrence ofabcin the pattern—there are none. - Next, we check if any prefix of
abcmatches a suffix ofabc: the longest such match is 0 (sincea≠c,ab≠bc). - So the move distance after a full match is
m - longest_prefix_suffix_match = 3 - 0 = 3.
For partial matches (e.g., matching only the last character c), the strong good suffix rule would give a move distance of 3 (since no other c exists in the pattern, and no prefix matches c), which is identical to the bad character rule for non-pattern characters.
Algorithm Execution & Comparison Counting
1. Target String: aabcbcbabcabcabc (Length 16)
We compare characters from right to left, counting each comparison, and use the strong good suffix rule to move after full matches.
| Step | Action | Comparison Count (Cumulative) |
|---|---|---|
| 1 | Compare s[2] = 'b' vs p[2] = 'c' (no match). Move 1 via bad character rule. | 1 |
| 2 | Compare s[3] = 'c' vs p[2] = 'c' (match). Then s[2] = 'b' vs p[1] = 'b' (match). Then s[1] = 'a' vs p[0] = 'a' (match). Full match found. Move 3 via strong good suffix rule. | 4 |
| 3 | Compare s[6] = 'b' vs p[2] = 'c' (no match). Move 1 via bad character rule. | 5 |
| 4 | Compare s[7] = 'a' vs p[2] = 'c' (no match). Move 2 via bad character rule. | 6 |
| 5 | Compare s[9] = 'c' vs p[2] = 'c' (match). Then s[8] = 'b' vs p[1] = 'b' (match). Then s[7] = 'a' vs p[0] = 'a' (match). Full match found. Move 3 via strong good suffix rule. | 9 |
| 6 | Compare s[12] = 'c' vs p[2] = 'c' (match). Then s[11] = 'b' vs p[1] = 'b' (match). Then s[10] = 'a' vs p[0] = 'a' (match). Full match found. Move 3 via strong good suffix rule. | 12 |
| 7 | Compare s[15] = 'c' vs p[2] = 'c' (match). Then s[14] = 'b' vs p[1] = 'b' (match). Then s[13] = 'a' vs p[0] = 'a' (match). Full match found. Move 3 (exceeds string length, end). | 15 |
Total comparisons: 15
Matches found: 4 (positions 1-3, 7-9, 10-12, 13-15)
2. Target String: abababababababab (Length 16)
This string has no c characters, so we'll never get a partial or full match.
| Step | Action | Comparison Count (Cumulative) |
|---|---|---|
| 1 | Compare s[2] = 'a' vs p[2] = 'c' (no match). Move 2 via bad character rule. | 1 |
| 2 | Compare s[4] = 'a' vs p[2] = 'c' (no match). Move 2 via bad character rule. | 2 |
| 3 | Compare s[6] = 'a' vs p[2] = 'c' (no match). Move 2 via bad character rule. | 3 |
| 4 | Compare s[8] = 'a' vs p[2] = 'c' (no match). Move 2 via bad character rule. | 4 |
| 5 | Compare s[10] = 'a' vs p[2] = 'c' (no match). Move 2 via bad character rule. | 5 |
| 6 | Compare s[12] = 'a' vs p[2] = 'c' (no match). Move 2 via bad character rule. | 6 |
| 7 | Compare s[14] = 'a' vs p[2] = 'c' (no match). Move 2 (exceeds string length, end). | 7 |
Total comparisons: 7
Matches found: 0
Key Takeaway for Short Patterns
For patterns as short as 3 characters, the strong good suffix rule rarely gives a better move than the bad character rule during partial mismatches. However, it's critical for full matches: it ensures we skip the entire matched pattern length (3 in this case) instead of potentially smaller moves from the bad character rule, which avoids redundant comparisons.
内容的提问来源于stack exchange，提问作者Alia
