এই সমস্যায়, আমাদেরকে একটি ইনপুট স্ট্রিং এবং একটি অ্যারে দেওয়া হয়েছে। আমাদের কাজ হল স্ট্রিং-এ অ্যারের সমস্ত শব্দের সমস্ত ঘটনা খুঁজে বের করা। এর জন্য, আমরা প্যাটার্ন অনুসন্ধানের জন্য Aho-Corasick অ্যালগরিদম ব্যবহার করব৷
স্ট্রিং এবং প্যাটার্ন অনুসন্ধান প্রোগ্রামিং একটি গুরুত্বপূর্ণ জিনিস. এবং প্রোগ্রামিং-এ, অ্যালগরিদম যত ভালো হবে তত বেশি ব্যবহারিক ব্যবহার করা যাবে। আহো-কোরাসিক অ্যালগরিদম এটি একটি খুব গুরুত্বপূর্ণ এবং শক্তিশালী অ্যালগরিদম যা স্ট্রিং অনুসন্ধানকে সহজ করে তোলে . এটি এক ধরণের অভিধানের সাথে মিলে যাওয়া অ্যালগরিদম, একই সাথে সমস্ত স্ট্রিংকে মেলে৷ অ্যালগরিদম ট্রাই ডেটা স্ট্রাকচার ব্যবহার করে এর বাস্তবায়নের জন্য।
ডেটা স্ট্রাকচার চেষ্টা করুন
Trie হল এক ধরনের প্রিফিক্স ট্রি বা একটি ডিজিটাল সার্চ ট্রি, যেখানে প্রতিটি প্রান্তকে কিছু অক্ষর দ্বারা লেবেল করা হয় (প্রতিটি বহির্গামী প্রান্তে বিভিন্ন অক্ষর থাকে) .
আহো-কোরাসিক বোঝার জন্য একটি উদাহরণ নেওয়া যাক অ্যালগরিদম
ইনপুট
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=ম্যাচের সংখ্যা।
বাস্তবায়ন
আহো-কোরাসিক অ্যালগরিদম এই সহজ ধাপগুলি দিয়ে তৈরি করা যেতে পারে
-
সারি ব্যবহার করে ট্রাই তৈরি করুন যাতে আমরা সারিতে থাকা প্রতিটি অক্ষরকে নোড ও 'ট্রাই' হিসাবে পপ করতে পারি।
-
ব্যর্থতা লিঙ্কগুলি (প্রত্যয় লিঙ্ক) একটি অ্যারে হিসাবে তৈরি করুন যা পরবর্তী এবং বর্তমান অক্ষর সংরক্ষণ করতে পারে
-
মিলিত শব্দগুলি সংরক্ষণ করার জন্য একটি অ্যারে হিসাবে আউটপুট লিঙ্কগুলি তৈরি করুন
-
সমস্ত অক্ষর চেক করতে একটি ট্রাভার্স ফাংশন (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
