数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会科学
时尚研究
法律研究错误字符启发法
错误字符启发法是 Boyer Moore 算法的一种方法。另一种方法是 Good Suffix Heuristic（好后缀启发法）。这种方法中，我们将尝试找到一个错误字符，这意味着是主字符串中的一个字符，与模式不匹配。当发生失配时，我们将移动整个模式，直到失配变成匹配，否则，模式移过错误字符。
此处的最佳时间复杂度为 O(m/n)，最坏情况下的时间复杂度为 O(mn)，其中 n 为文本长度，m 为模式长度。
输入和输出
Input: Main String: “ABAAABCDBBABCDDEBCABC”, Pattern “ABC” Output: Pattern found at position: 4 Pattern found at position: 10 Pattern found at position: 18
算法
badCharacterHeuristic(pattern, badCharacterArray)
输入 − pattern，要搜索的模式，将错误字符数组存储在 locations
输出：填充错误字符数组以备将来使用
Begin n := pattern length for all entries of badCharacterArray, do set all entries to -1 done for all characters of the pattern, do set last position of each character in badCharacterArray. done End
searchPattern(pattern, text)
输入 − pattern，要搜索的模式和主文本
输出 − 找到模式的位置
Begin patLen := length of pattern strLen := length of text. call badCharacterHeuristic(pattern, badCharacterArray) shift := 0 while shift <= (strLen - patLen), do j := patLen -1 while j >= 0 and pattern[j] = text[shift + j], do decrease j by 1 done if j < 0, then print the shift as, there is a match if shift + patLen < strLen, then shift:= shift + patLen – badCharacterArray[text[shift + patLen]] else increment shift by 1 else shift := shift + max(1, j-badCharacterArray[text[shift+j]]) done End
示例
#include<iostream>
#define MAXCHAR 256
using namespace std;
int maximum(int data1, int data2) {
if(data1 > data2)
return data1;
return data2;
}
void badCharacterHeuristic(string pattern, int badCharacter[MAXCHAR]) {
int n = pattern.size(); //find length of pattern
for(int i = 0; i<MAXCHAR; i++)
badCharacter[i] = -1; //set all character distance as -1
for(int i = 0; i < n; i++) {
badCharacter[(int)pattern[i]] = i; //set position of character in the array.
}
}
void searchPattern(string mainString, string pattern, int *array, int *index) {
int patLen = pattern.size();
int strLen = mainString.size();
int badCharacter[MAXCHAR]; //make array for bad character position
badCharacterHeuristic(pattern, badCharacter); //fill bad character array
int shift = 0;
while(shift <= (strLen - patLen)) {
int j = patLen - 1;
while(j >= 0 && pattern[j] == mainString[shift+j]) {
j--; //reduce j when pattern and main string character is matching
}
if(j < 0) {
(*index)++;
array[(*index)] = shift;
if((shift + patLen) < strLen) {
shift += patLen - badCharacter[mainString[shift + patLen]];
}else {
shift += 1;
}
}else {
shift += maximum(1, j - badCharacter[mainString[shift+j]]);
}
}
}
int main() {
string mainString = "ABAAABCDBBABCDDEBCABC";
string pattern = "ABC";
int locArray[mainString.size()];
int index = -1;
searchPattern(mainString, pattern, locArray, &index);
for(int i = 0; i <= index; i++) {
cout << "Pattern found at position: " << locArray[i]<<endl;
}
}输出
Pattern found at position: 4 Pattern found at position: 10 Pattern found at position: 18
更新时间：2020 年 6 月 15 日
1K+ 浏览
广告