資料結構
網路
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+ 瀏覽
廣告