資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++ 中的 Aho-Corasick 演算法用於模式搜尋
在這個問題中，我們給定一個輸入字串和一個數組 arr[]。我們的任務是在字串中查詢陣列中所有單詞的所有出現位置。為此，我們將使用 **Aho-Corasick 演算法進行模式搜尋**。
字串和模式搜尋是程式設計中一項重要內容。在程式設計中，演算法越好，其實際應用就越多。**Aho-Corasick 演算法**是一種 *非常重要且強大的演算法，它使字串搜尋變得容易*。它是一種字典匹配演算法，可以同時匹配所有字串。該演算法使用 *Trie 資料結構* 來實現。
Trie 資料結構
Trie 是一種 *字首樹或數字搜尋樹，其中每條邊都用某個字母標記（每條出邊具有不同的字母）*。
讓我們舉個例子來理解 *Aho-Corasick* 演算法
**輸入**
string = "bheythisghisanexample"
arr[] = {"hey", "this", "is", "an", “example”}**輸出**
Word hey starts from 2 Word this starts from 5 Word is starts from 11 Word an starts from 13 Word example starts from 15
該演算法的時間複雜度為 **O(N+L+Z)**，其中 N=輸入字串/文字的長度
L=關鍵字（陣列中的單詞）的長度
Z=匹配次數。
實現
Aho-Corasick 演算法可以透過以下簡單的步驟構建
使用佇列構建 Trie，以便我們可以將佇列中的每個字元彈出作為“Trie”的節點。
構建失效連結（字尾連結）作為陣列，可以儲存下一個和當前字元
構建輸出連結作為陣列以儲存匹配的單詞
構建遍歷函式 (FindNextState) 來檢查所有字元。
**失效連結（字尾連結）** - 當我們遇到無法繼續讀取字元的字串部分時，我們會透過遵循字尾連結回退，以嘗試保留儘可能多的上下文。簡而言之，它儲存當 Trie 中當前字元沒有邊時所遵循的所有邊。
**輸出連結** - 它始終指向對應於當前狀態中存在的最長單詞的節點，我們確保使用輸出連結將所有模式連結在一起。
示例
#include<iostream>
#include <string.h>
#include<algorithm>
#include<queue>
using namespace std;
const int MaxStates = 6 * 50 + 10;
const int MaxChars = 26;
int OccurenceOfWords[MaxStates];
int FF[MaxStates];
int GotoFunction[MaxStates][MaxChars];
int BuildMatchingMachine(const vector<string> &words, char lowestChar = 'a', char highestChar = 'z'){
memset(OccurenceOfWords, 0, sizeof OccurenceOfWords);
memset(FF, -1, sizeof FF);
memset(GotoFunction, -1, sizeof GotoFunction);
int states = 1;
for (int i = 0; i < words.size(); ++i){
const string &keyword = words[i];
int currentState = 0;
for (int j = 0; j < keyword.size(); ++j){
int c = keyword[j] - lowestChar;
if (GotoFunction[currentState][c] == -1){
GotoFunction[currentState][c] = states++;
}
currentState = GotoFunction[currentState][c];
}
OccurenceOfWords[currentState] |= (1 << i);
}
for (int c = 0; c < MaxChars; ++c){
if (GotoFunction[0][c] == -1){
GotoFunction[0][c] = 0;
}
}
queue<int> q;
for (int c = 0; c <= highestChar - lowestChar; ++c){
if (GotoFunction[0][c] != -1 && GotoFunction[0][c] != 0){
FF[GotoFunction[0][c]] = 0;
q.push(GotoFunction[0][c]);
}
}
while (q.size()){
int state = q.front();
q.pop();
for (int c = 0; c <= highestChar - lowestChar; ++c){
if (GotoFunction[state][c] != -1){
int failure = FF[state];
while (GotoFunction[failure][c] == -1){
failure = FF[failure];
}
failure = GotoFunction[failure][c];
FF[GotoFunction[state][c]] = failure;
OccurenceOfWords[GotoFunction[state][c]] |= OccurenceOfWords[failure];
q.push(GotoFunction[state][c]);
}
}
}
return states;
}
int FindNextState(int currentState, char nextInput, char lowestChar = 'a'){
int answer = currentState;
int c = nextInput - lowestChar;
while (GotoFunction[answer][c] == -1){
answer = FF[answer];
}
return GotoFunction[answer][c];
}
vector<int> FindWordCount(string str, vector<string> keywords, char lowestChar = 'a', char highestChar = 'z') {
BuildMatchingMachine(keywords, lowestChar, highestChar);
int currentState = 0;
vector<int> retVal;
for (int i = 0; i < str.size(); ++i){
currentState = FindNextState(currentState, str[i], lowestChar);
if (OccurenceOfWords[currentState] == 0)
continue;
for (int j = 0; j < keywords.size(); ++j){
if (OccurenceOfWords[currentState] & (1 << j)){
retVal.insert(retVal.begin(), i - keywords[j].size() + 1);
}
}
}
return retVal;
}
int main(){
vector<string> keywords;
keywords.push_back("All");
keywords.push_back("she");
keywords.push_back("is");
string str = "Allisheall";
cout<<"The occurrences of all words in the string ' "<<str<<" ' are \n";
vector<int> states = FindWordCount(str, keywords);
for(int i=0; i < keywords.size(); i++){
cout<<"Word "<<keywords.at(i)<<' ';
cout<<"starts at "<<states.at(i)+1<<' ';
cout<<"And ends at "<<states.at(i)+keywords.at(i).size()+1<<endl;
}
}輸出
The occurrences of all words in the string ' Allisheall ' are Word All starts at 5 And ends at 8 Word she starts at 4 And ends at 7 Word is starts at 1 And ends at 3
更新於：2020-08-06
677 次瀏覽
廣告