Boyer Moore 算法
Boyer Moore 模式匹配算法
Boyer Moore 算法用于确定给定模式是否存在于指定文本中。它遵循一种后向的模式搜索/匹配方法。在给定字符串中搜索特定模式的任务称为模式搜索问题。例如，如果文本为"THIS IS A SAMPLE TEXT"，模式为"TEXT"，则输出应为 10，这是给定文本中模式首次出现的索引。
该算法由 Robert Boyer 和 J Strother Moore 于 1977 开发。它被认为是最高效、应用最广泛的模式匹配算法。
Boyer Moore 算法是如何工作的？
在前面的章节中，我们了解了解决这个问题的简单方法，即将模式逐个滑过文本并比较每个字符。然而，这种方法非常慢，因为它需要 O(n*m) 的时间复杂度，其中 n 是文本的长度，m 是模式的长度。Boyer Moore 算法 通过预处理模式并使用两种启发式算法跳过一些不会匹配的比较来改进这个问题。
这两种启发式算法如下 −
不良字符启发式算法 − 此启发式算法使用一个表来存储模式中每个字符的最后一次出现。当文本中某个字符（坏字符）出现不匹配时，算法会检查该字符是否出现在模式中。如果出现，算法会移动模式，使该字符在模式中的最后一次出现与文本中的坏字符对齐。如果没有出现，算法会将模式移到坏字符之后。
好的后缀启发式 − 当坏启发式失败时，该启发式使用另一个表来存储移位信息。在这种情况下，我们会在模式中查找，直到坏字符成为文本的好的后缀。然后我们继续移动以找到给定的模式。
Boyer-Moore 算法结合了这两种启发式，在每一步中选择它们建议的最大移位。在此过程中，从模式的最后一个字符开始搜索子字符串或模式。当主字符串的子字符串与模式的子字符串匹配时，算法会继续查找匹配子字符串的其他位置。如果不匹配，算法会应用启发式算法并相应地移动模式。当找到完全匹配或到达文本末尾时，算法会停止。
Boyer-Moore 算法的最坏情况时间复杂度为 O(nm)，但它的性能可以远高于此。事实上，在某些情况下，它可以达到 O(n/m) 的亚线性时间复杂度，这意味着它可以跳过文本中的某些字符而不进行比较。当模式中没有重复字符或字母表大小较大时，就会发生这种情况。
为了说明 Boyer-Moore 算法的工作原理，我们来看一个例子 −
输入： 主字符串："AABAAABCEDBABCDDEBC" 模式："ABC" 输出： 在以下位置找到模式： 5 在以下位置找到模式： 11
示例
在下面的例子中，我们将说明 Boyer-Moore 算法在各种编程语言中的工作原理。
#include<stdio.h>
#include<string.h>
// 完整后缀匹配函数
void computeFullShift(int shiftArr[], int longSuffArr[], char patrn[], int n) {
int i = n;
int j = n+1;
longSuffArr[i] = j;
while(i > 0) {
// 如果第 (i-1) 项和第 (j-1) 项不相同，则向右搜索
while(j <= n && patrn[i-1] != patrn[j-1] ) {
// 将模式从 i 转移到 j
if(shiftArr[j] == 0) {
shiftArr[j] = j-i;
}
// 更新长后缀值
j = longSuffArr[j];
}
i--;
j--;
longSuffArr[i] = j;
}
}
// 良好后缀匹配函数
void computeGoodSuffix(int shiftArr[], int longSuffArr[], char patrn[], int n) {
int j;
j = longSuffArr[0];
// 循环遍历模式
for(int i = 0; i<n; i++) {
// 将移位设置为长后缀值
if(shiftArr[i] == 0) {
shiftArr[i] = j;
if(i == j) {
// 更新长后缀值
j = longSuffArr[j];
}
}
}
}
// 搜索模式的功能
void searchPattern(char orgnStr[], char patrn[], int array[], int *index) {
// 模式长度
int patLen = strlen(patrn);
// 主字符串长度
int strLen = strlen(orgnStr);
int longerSuffArray[patLen+1];
int shiftArr[patLen + 1];
// 将 shift 数组元素初始化为 0
for(int i = 0; i<=patLen; i++) {
shiftArr[i] = 0;
}
// 调用 computeFullShift 函数
computeFullShift(shiftArr, longerSuffArray, patrn, patLen);
// 调用 computeGoodSuffix 函数
computeGoodSuffix(shiftArr, longerSuffArray, patrn, patLen);
int shift = 0;
while(shift <= (strLen - patLen)) {
int j = patLen - 1;
// 当模式和主字符串字符匹配时，减少 j
while(j >= 0 && patrn[j] == orgnStr[shift+j]) {
j--;
}
if(j < 0) {
(*index)++;
// 存储找到模式的位置
array[(*index)] = shift;
shift += shiftArr[0];
}else {
shift += shiftArr[j+1];
}
}
}
int main() {
// 原始字符串
char orgnStr[] = "AABAAABCEDBABCDDEBC";
// 要搜索的模式
char patrn[] = "ABC";
// 用于存储找到模式的位置的数组
int locArray[strlen(orgnStr)];
int index = -1;
// 调用 searchPattern 函数
searchPattern(orgnStr, patrn, locArray, &index);
// 打印找到模式的位置
for(int i = 0; i <= index; i++) {
printf("在以下位置找到图案： %d
", locArray[i]);
}
return 0;
}
#include<iostream>
using namespace std;
// 完整后缀匹配函数
void computeFullShift(int shiftArr[], int longSuffArr[], string patrn) {
// 模式的长度
int n = patrn.size();
int i = n;
int j = n+1;
longSuffArr[i] = j;
while(i > 0) {
// 如果第 (i-1) 项和第 (j-1) 项不相同，则向右搜索
while(j <= n && patrn[i-1] != patrn[j-1] ) {
// 将模式从 i 转移到 j
if(shiftArr[j] == 0) {
shiftArr[j] = j-i;
}
// 更新长后缀值
j = longSuffArr[j];
}
i--;
j--;
longSuffArr[i] = j;
}
}
// 良好后缀匹配函数
void computeGoodSuffix(int shiftArr[], int longSuffArr[], string patrn) {
// 模式的长度
int n = patrn.size();
int j;
j = longSuffArr[0];
// 循环遍历模式
for(int i = 0; i<n; i++) {
// 将移位设置为长后缀值
if(shiftArr[i] == 0) {
shiftArr[i] = j;
if(i == j) {
// 更新长后缀值
j = longSuffArr[j];
}
}
}
}
// 搜索模式的功能
void searchPattern(string orgnStr, string patrn, int array[], int *index) {
// 模式的长度
int patLen = patrn.size();
// 主字符串的长度
int strLen = orgnStr.size();
int longerSuffArray[patLen+1];
int shiftArr[patLen + 1];
// 将 shift 数组元素初始化为 0
for(int i = 0; i<=patLen; i++) {
shiftArr[i] = 0;
}
// 调用 computeFullShift 函数
computeFullShift(shiftArr, longerSuffArray, patrn);
// 调用 computeGoodSuffix 函数
computeGoodSuffix(shiftArr, longerSuffArray, patrn);
int shift = 0;
while(shift <= (strLen - patLen)) {
int j = patLen - 1;
// 当模式和主字符串字符匹配时，减少 j
while(j >= 0 && patrn[j] == orgnStr[shift+j]) {
j--;
}
if(j < 0) {
(*index)++;
// 存储找到模式的位置
array[(*index)] = shift;
shift += shiftArr[0];
}else {
shift += shiftArr[j+1];
}
}
}
int main() {
// 原始字符串
string orgnStr = "AABAAABCEDBABCDDEBC";
// 要搜索的模式
string patrn = "ABC";
// 用于存储找到模式的位置的数组
int locArray[orgnStr.size()];
int index = -1;
// 调用 searchPattern 函数
searchPattern(orgnStr, patrn, locArray, &index);
// 打印找到模式的位置
for(int i = 0; i <= index; i++) {
cout << "在以下位置找到图案： " << locArray[i]<<endl;
}
}
public class BMalgo {
// 完整后缀匹配方法
static void computeFullShift(int[] shiftArr, int[] longSuffArr, String patrn) {
// 模式的长度
int n = patrn.length();
int i = n;
int j = n+1;
longSuffArr[i] = j;
while(i > 0) {
// 如果第 (i-1) 项和第 (j-1) 项不相同，则向右搜索
while(j <= n && patrn.charAt(i-1) != patrn.charAt(j-1)) {
// 将模式从 i 转移到 j
if(shiftArr[j] == 0) {
shiftArr[j] = j-i;
}
// 更新长后缀值
j = longSuffArr[j];
}
i--;
j--;
longSuffArr[i] = j;
}
}
// 良好后缀匹配的方法
static void computeGoodSuffix(int[] shiftArr, int[] longSuffArr, String patrn) {
// 模式的长度
int n = patrn.length();
int j;
j = longSuffArr[0];
// 循环遍历模式
for(int i = 0; i<n; i++) {
// 将移位设置为长后缀值
if(shiftArr[i] == 0) {
shiftArr[i] = j;
if(i == j) {
// 更新长后缀值
j = longSuffArr[j];
}
}
}
}
// 搜索模式的方法
static void searchPattern(String orgnStr, String patrn, int[] array, int[] index) {
// 模式的长度
int patLen = patrn.length();
// 主字符串的长度
int strLen = orgnStr.length();
int[] longerSuffArray = new int[patLen+1];
int[] shiftArr = new int[patLen + 1];
// 将 shift 数组元素初始化为 0
for(int i = 0; i<=patLen; i++) {
shiftArr[i] = 0;
}
// 调用 computeFullShift 方法
computeFullShift(shiftArr, longerSuffArray, patrn);
// 调用 computeGoodSuffix 方法
computeGoodSuffix(shiftArr, longerSuffArray, patrn);
int shift = 0;
while(shift <= (strLen - patLen)) {
int j = patLen - 1;
// 当模式和主字符串字符匹配时，减少 j
while(j >= 0 && patrn.charAt(j) == orgnStr.charAt(shift+j)) {
j--;
}
if(j < 0) {
index[0]++;
// 存储找到模式的位置
array[index[0]] = shift;
shift += shiftArr[0];
}else {
shift += shiftArr[j+1];
}
}
}
public static void main(String[] args) {
// 原始字符串
String orgnStr = "AABAAABCEDBABCDDEBC";
// 要搜索的模式
String patrn = "ABC";
// 用于存储找到模式的位置的数组
int[] locArray = new int[orgnStr.length()];
int[] index = {-1};
// 调用 searchPattern 方法
searchPattern(orgnStr, patrn, locArray, index);
// 打印找到模式的位置
for(int i = 0; i <= index[0]; i++) {
System.out.println("在以下位置找到图案： " + locArray[i]);
}
}
}
# 完整后缀匹配函数
def compute_full_shift(shift_arr, long_suff_arr, patrn):
# 模式长度
n = len(patrn)
i = n
j = n+1
long_suff_arr[i] = j
while i > 0:
# 如果第 (i-1) 项和第 (j-1) 项不相同，则向右搜索
while j <= n and patrn[i-1] != patrn[j-1]:
# 将模式从 i 转移到 j
if shift_arr[j] == 0:
shift_arr[j] = j-i
# 更新长后缀值
j = long_suff_arr[j]
i -= 1
j -= 1
long_suff_arr[i] = j
# 良好后缀匹配函数
def compute_good_suffix(shift_arr, long_suff_arr, patrn):
# 模式长度
n = len(patrn)
j = long_suff_arr[0]
# 循环遍历模式
for i in range(n):
# 将移位设置为长后缀值
if shift_arr[i] == 0:
shift_arr[i] = j
if i == j:
# 更新长后缀值
j = long_suff_arr[j]
# 搜索模式的功能
def search_pattern(orgn_str, patrn, array, index):
# 模式长度
pat_len = len(patrn)
# 主字符串长度
str_len = len(orgn_str)
longer_suff_array = [0]*(pat_len+1)
shift_arr = [0]*(pat_len + 1)
# 将移位数组元素初始化为 0
for i in range(pat_len+1):
shift_arr[i] = 0
# 调用 compute_full_shift 函数
compute_full_shift(shift_arr, longer_suff_array, patrn)
# 调用 compute_good_suffix 函数
compute_good_suffix(shift_arr, longer_suff_array, patrn)
shift = 0
while shift <= (str_len - pat_len):
j = pat_len - 1
# 当模式和主字符串字符匹配时，减少 j
while j >= 0 and patrn[j] == orgn_str[shift+j]:
j -= 1
if j < 0:
index[0] += 1
# 存储找到模式的位置
array[index[0]] = shift
shift += shift_arr[0]
else:
shift += shift_arr[j+1]
# 原始字符串
orgn_str = "AABAAABCEDBABCDDEBC"
# 待搜索的模式
patrn = "ABC"
# 用于存储模式位置的数组
loc_array = [0]*len(orgn_str)
index = [-1]
# 调用 search_pattern 函数
search_pattern(orgn_str, patrn, loc_array, index)
# 打印模式位置
for i in range(index[0]+1):
print("在以下位置找到图案： ", loc_array[i])
输出
在以下位置找到图案： 5 在以下位置找到图案： 11
