সি++-এ আহো-কোরাসিক অ্যালগরিদম (Aho-Corasick) প্যাটার্ন সার্চিং

একটি ইনপুট স্ট্রিং এবং কীওয়ার্ড অ্যারে দেওয়া আছে। আহো-কোরাসিক অ্যালগরিদম ব্যবহার করে স্ট্রিং-এ সব কীওয়ার্ডের সকল অকারেন্স খুঁজে বের করতে হবে। এটি ট্রাই (Trie) ডেটা স্ট্রাকচার ব্যবহার করে একসাথে মাল্টিপল প্যাটার্ন ম্যাচ করে।

ট্রাই (Trie) ডেটা স্ট্রাকচার

ট্রাই হলো প্রিফিক্স ট্রি যেখানে প্রতিটি এজ একটি ক্যারেক্টার দিয়ে লেবেল্ড।

ইনপুট

string = "bheythisghisanexample", arr = {"hey", "this", "is", "an", "example"}

আউটপুট

Word hey at 2, this at 5, is at 11, an at 13, example at 15

কমপ্লেক্সিটি

O(N + L + Z), N = স্ট্রিং দৈর্ঘ্য, L = কীওয়ার্ডগুলোর মোট দৈর্ঘ্য, Z = ম্যাচ সংখ্যা।

বাস্তবায়ন ধাপ

• ট্রাই নির্মাণ (Goto ফাংশন)।
• ফেইলার লিংক (Suffix link) তৈরি।
• আউটপুট লিংক তৈরি।
• ট্রাভার্স ফাংশন (FindNextState) দিয়ে স্ট্রিং স্ক্যান।

উদাহরণ কোড

#include <iostream> 
#include <string.h> 
#include <algorithm> 
#include <queue> 
#include <vector> 
using namespace std; 

const int MaxStates = 6*50+10, MaxChars = 26;
int out[MaxStates], fail[MaxStates], go[MaxStates][MaxChars];

int buildMachine(vector &words, char low='a', char high='z'){
    memset(out, 0, sizeof out);
    memset(fail, -1, sizeof fail);
    memset(go, -1, sizeof go);
    int states = 1;
    for(int i=0; i q;
    for(int c=0; c<=high-low; c++)
        if(go[0][c]!=0){ fail[go[0][c]]=0; q.push(go[0][c]); }
    while(!q.empty()){
        int state = q.front(); q.pop();
        for(int c=0; c<=high-low; c++)
            if(go[state][c]!=-1){
                int f = fail[state];
                while(go[f][c]==-1) f = fail[f];
                f = go[f][c];
                fail[go[state][c]] = f;
                out[go[state][c]] |= out[f];
                q.push(go[state][c]);
            }
    }
    return states;
}

int nextState(int cur, char ch, char low='a'){
    int c = ch - low;
    while(go[cur][c]==-1) cur = fail[cur];
    return go[cur][c];
}

vector findWords(string str, vector &words, char low='a', char high='z'){
    buildMachine(words, low, high);
    int cur = 0; vector res;
    for(int i=0; i kw = {"All", "she", "is"};
    string str = "Allisheall";
    auto pos = findWords(str, kw);
    for(int i=0; i

আউটপুট
All at 1, she at 4, is at 1