इस समस्या में, हमें एक इनपुट स्ट्रिंग और एक सरणी arr[] दी गई है। हमारा कार्य सरणी के सभी शब्दों की स्ट्रिंग में सभी घटनाओं को ढूंढना है। इसके लिए, हम पैटर्न खोज के लिए अहो-कोरासिक एल्गोरिदम का उपयोग करेंगे।
स्ट्रिंग और पैटर्न खोज प्रोग्रामिंग में एक महत्वपूर्ण चीज है। और प्रोग्रामिंग में, एल्गोरिदम जितना बेहतर होगा उतना ही अधिक व्यावहारिक उपयोग हो सकता है। अहो-कोरासिक एल्गोरिदम एक बहुत महत्वपूर्ण और शक्तिशाली एल्गोरिदम है जो स्ट्रिंग खोज को आसान बनाता है. यह एक प्रकार का डिक्शनरी मिलान एल्गोरिदम है, जो सभी स्ट्रिंग्स को एक साथ मिलान करता है। एल्गोरिदम अपने कार्यान्वयन के लिए ट्राई डेटा संरचना का उपयोग करता है।
ट्राई डेटा संरचना
ट्राई एक प्रकार का प्रीफिक्स ट्री या डिजिटल खोज ट्री है, जहां प्रत्येक किनारा किसी अक्षर द्वारा लेबल किया जाता है (प्रत्येक आउटगोइंग किनारे में अलग-अलग अक्षर होते हैं)।
आइए अहो-कोरासिक एल्गोरिदम को समझने के लिए एक उदाहरण लेते हैं
इनपुट
string = "bheythisghisanexample" arr[] = {"hey", "this", "is", "an", "example"}
आउटपुट
शब्द hey 2 से शुरू होता है शब्द this 5 से शुरू होता है शब्द is 11 से शुरू होता है शब्द an 13 से शुरू होता है शब्द example 15 से शुरू होता है
इस एल्गोरिदम की समय जटिलता O(N+L+Z) है, जहां N= इनपुट स्ट्रिंग/टेक्स्ट की लंबाई
L= कीवर्ड्स की लंबाई (सरणी में शब्द)
Z= मिलानों की संख्या।
कार्यान्वयन
अहो-कोरासिक एल्गोरिदम को इन आसान चरणों के साथ बनाया जा सकता है:
- क्यू का उपयोग करके ट्राई का निर्माण करें ताकि हम क्यू में प्रत्येक वर्ण को 'ट्राई' के नोड के रूप में पॉप कर सकें।
- विफलता लिंक्स (सफिक्स लिंक्स) को एक सरणी के रूप में बनाएं जो अगले और वर्तमान वर्ण को संग्रहीत कर सके।
- आउटपुट लिंक्स को एक सरणी के रूप में बनाएं जो मिलान करने वाले शब्दों को संग्रहीत कर सके।
- एक ट्रैवर्स फ़ंक्शन (FindNextState) बनाएं ताकि सभी वर्णों की जांच की जा सके।
विफलता लिंक (सफिक्स लिंक) - जब हम स्ट्रिंग के उस हिस्से पर पहुंचते हैं जहां हम वर्णों को पढ़ना जारी नहीं रख सकते, तो हम संदर्भ को यथासंभव संरक्षित करने के लिए सफिक्स लिंक्स का पालन करके पीछे हटते हैं। संक्षेप में, यह उन सभी किनारों को संग्रहीत करता है जिनका पालन तब किया जाता है जब वर्तमान वर्ण का ट्राई में कोई किनारा नहीं होता।
आउटपुट लिंक - यह हमेशा उस नोड की ओर इशारा करता है जो वर्तमान स्थिति में मौजूद सबसे लंबे शब्द से मेल खाता है, हम यह सुनिश्चित करते हैं कि हम आउटपुट लिंक्स का उपयोग करके सभी पैटर्न को एक साथ जोड़ते हैं।
उदाहरण
#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 << "स्ट्रिंग '" << str << "' में सभी शब्दों की घटनाएं हैं \n";
vector<int> states = FindWordCount(str, keywords);
for (int i = 0; i < keywords.size(); i++) {
cout << "शब्द " << keywords.at(i) << "' ";
cout << "शुरू होता है " << states.at(i) + 1 << "' ";
cout << "और समाप्त होता है " << states.at(i) + keywords.at(i).size() + 1 << endl;
}
}
आउटपुट
स्ट्रिंग ' Allisheall ' में सभी शब्दों की घटनाएं हैं शब्द All 5 पर शुरू होता है और 8 पर समाप्त होता है शब्द she 4 पर शुरू होता है और 7 पर समाप्त होता है शब्द is 1 पर शुरू होता है और 3 पर समाप्त होता है