三、BM 算法實(shí)現(xiàn)與代碼解析

（一）預(yù)處理階段

壞字符表構(gòu)建：壞字符表（Bad Character Table）的構(gòu)建是預(yù)處理階段的關(guān)鍵任務(wù)之一。其目的是為了在匹配過程中，當(dāng)遇到不匹配的字符（即壞字符）時(shí)，能夠快速確定模式串應(yīng)該向右滑動(dòng)的距離。在 Python 中，我們可以使用哈希表（字典）來實(shí)現(xiàn)這一功能 。

def build_bad_char_table(pattern):

bad_char = {}

for i in range(len(pattern) - 1):

bad_char[pattern[i]] = i

return bad_char

這段代碼通過遍歷模式串，將每個(gè)字符作為鍵，其在模式串中的位置作為值，存儲(chǔ)在哈希表bad_char中。例如，對(duì)于模式串 "ABABC"，哈希表中會(huì)記錄'A': 0, 'B': 1, 'C': 4（這里只記錄到倒數(shù)第二個(gè)字符，因?yàn)樽詈笠粋€(gè)字符在匹配時(shí)用于判斷是否完全匹配，不需要單獨(dú)記錄其位置）。這種方式使得在匹配過程中查詢壞字符的位置時(shí)間復(fù)雜度為\(O(1)\)，極大地提高了匹配效率。

除了哈希表，也可以使用數(shù)組來存儲(chǔ)壞字符的位置信息。如果字符集是有限且已知的，例如 ASCII 字符集（共 128 個(gè)字符），可以創(chuàng)建一個(gè)大小為 128 的數(shù)組bc，初始值全部設(shè)為 -1 。然后遍歷模式串，對(duì)于每個(gè)字符pattern[i]，將bc[ord(pattern[i])]設(shè)置為i。這樣在查詢時(shí)，通過bc[ord(bad_character)]即可獲取壞字符在模式串中的位置，同樣支持\(O(1)\)時(shí)間復(fù)雜度的字符查詢。

好后綴表構(gòu)建：好后綴表（Good Suffix Table）的構(gòu)建相對(duì)復(fù)雜，它需要考慮模式串中后綴與前綴的匹配關(guān)系，以及后綴在模式串中的其他匹配位置。構(gòu)建好后綴表的核心邏輯在于通過后綴匹配和前綴檢查，生成每個(gè)位置對(duì)應(yīng)的滑動(dòng)距離。

def build_good_suffix_table(pattern):

m = len(pattern)

suffix = [-1] * m

prefix = [False] * m

for i in range(m - 1):

j = i

while j >= 0 and pattern[j] == pattern[m - 1 - i + j]:

j -= 1

suffix[m - 1 - i] = j + 1

for i in range(m - 1):

if suffix[i] == 0:

prefix[m - 1 - i] = True

for i in range(1, m):

j = m - 1 - suffix[i]

prefix[j] = True

good_suffix = [m] * m

for i in range(m - 2, -1, -1):

if prefix[i]:

good_suffix[i] = m - 1 - i

else:

good_suffix[i] = good_suffix[m - 1 - suffix[i]]

return good_suffix

在這段代碼中，首先通過一個(gè)雙重循環(huán)計(jì)算suffix數(shù)組，suffix[i]表示從模式串末尾開始長(zhǎng)度為i + 1的后綴，其最長(zhǎng)匹配后綴的長(zhǎng)度（即從模式串開頭開始的相同子串長(zhǎng)度）。例如，對(duì)于模式串 "ABABC"，當(dāng)i = 0時(shí)，后綴為 "C"，其最長(zhǎng)匹配后綴長(zhǎng)度為 0；當(dāng)i = 1時(shí)，后綴為 "BC"，其最長(zhǎng)匹配后綴長(zhǎng)度為 0；當(dāng)i = 2時(shí)，后綴為 "ABC"，其最長(zhǎng)匹配后綴長(zhǎng)度為 3（因?yàn)槟Ｊ酱_頭的 "ABC" 與之匹配），所以suffix[2] = 3 。

然后，通過檢查suffix數(shù)組，標(biāo)記出哪些位置的后綴是模式串的前綴，存儲(chǔ)在prefix數(shù)組中。最后，根據(jù)suffix和prefix數(shù)組生成good_suffix數(shù)組，good_suffix[i]表示當(dāng)在位置i匹配失敗時(shí)，根據(jù)好后綴規(guī)則模式串應(yīng)該向右滑動(dòng)的距離。如果prefix[i]為True，說明從位置i開始的后綴是模式串的前綴，此時(shí)滑動(dòng)距離為模式串長(zhǎng)度減去i；否則，滑動(dòng)距離為good_suffix[m - 1 - suffix[i]]，即根據(jù)之前計(jì)算的相同后綴的滑動(dòng)距離來確定。

（二）匹配階段

匹配階段是 BM 算法的核心執(zhí)行部分，它從主串的起始位置開始，將模式串與主串進(jìn)行對(duì)齊，并從模式串的末尾字符開始向前比較。

def boyer_moore_search(text, pattern):

n = len(text)

m = len(pattern)

bad_char = build_bad_char_table(pattern)

good_suffix = build_good_suffix_table(pattern)

s = 0

while s <= n - m:

j = m - 1

while j >= 0 and text[s + j] == pattern[j]:

j -= 1

if j < 0:

print(f"Pattern found at position {s}")

s += good_suffix[0]

else:

bad_char_shift = j - bad_char.get(text[s + j], -1)

good_suffix_shift = good_suffix[j]

s += max(bad_char_shift, good_suffix_shift)

在上述代碼中，外層循環(huán)控制模式串在主串中的滑動(dòng)位置s。每次循環(huán)開始時(shí)，將模式串的末尾字符與主串中對(duì)應(yīng)的字符進(jìn)行比較（通過內(nèi)層循環(huán)實(shí)現(xiàn)）。如果從模式串末尾開始的所有字符都與主串中對(duì)應(yīng)的字符匹配（即j < 0），則說明找到了一個(gè)匹配位置，打印出匹配位置，并根據(jù)好后綴表中的第一個(gè)值（good_suffix[0]）滑動(dòng)模式串，因?yàn)榇藭r(shí)整個(gè)模式串都匹配，按照好后綴規(guī)則移動(dòng)可以繼續(xù)尋找下一個(gè)可能的匹配位置 。

如果在比較過程中發(fā)現(xiàn)不匹配的字符，即壞字符，根據(jù)壞字符規(guī)則計(jì)算滑動(dòng)距離bad_char_shift，同時(shí)根據(jù)好后綴規(guī)則計(jì)算滑動(dòng)距離good_suffix_shift。然后取這兩個(gè)滑動(dòng)距離中的較大值，將模式串向右滑動(dòng)相應(yīng)的距離，繼續(xù)下一輪匹配。這樣，通過不斷地利用壞字符規(guī)則和好后綴規(guī)則，BM 算法能夠在主串中快速定位模式串的所有匹配位置，避免了大量不必要的字符比較操作，從而實(shí)現(xiàn)高效的字符串匹配。