이 문제에서는 입력 문자열과 배열 arr[]이 제공됩니다. 우리의 임무는 문자열에서 배열의 모든 단어의 모든 발생을 찾는 것입니다. 이를 위해 패턴 검색을 위한 Aho-Corasick 알고리즘을 사용할 것입니다.
문자열 및 패턴 검색은 프로그래밍에서 중요한 것입니다. 그리고 프로그래밍에서 알고리즘이 좋을수록 더 실용적으로 사용할 수 있습니다. Aho-Corasick 알고리즘 문자열 검색을 쉽게 해주는 매우 중요하고 강력한 알고리즘 . 모든 문자열을 동시에 일치시키는 일종의 사전 일치 알고리즘입니다. 알고리즘은 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를 구성하여 대기열의 각 문자를 노드 od '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