আহো-কোরাসিক অ্যালগরিদম (Aho-Corasick Algorithm)

আহো-কোরাসিক অ্যালগরিদম একাধিক কিয়ওয়ার্ডের সব অকারেন্স খুঁজে বের করার জন্য ডিকশনারি-ম্যাচিং অ্যালগরিদম। এটি ট্রি স্ট্রাকচার (ট্রাই) বানায়, তারপর অটোমেটনে রূপান্তর করে লিনিয়ার টাইমে সার্চ করে। তিনটি ফেজ: Go-to, Failure, Output।

কমপ্লেক্সিটি: O(N + L + Z)

• N = টেক্সট দৈর্ঘ্য, L = কিয়ওয়ার্ডগুলোর মোট দৈর্ঘ্য, Z = ম্যাচ সংখ্যা

ইনপুট এবং আউটপুট

Input: Patterns: {their, there, answer, any, bye}
       Text: "isthereanyanswerokgoodbye"
Output: Word there location: 2
        Word any location: 7
        Word answer location: 10
        Word bye location: 22

অ্যালগরিদম

buildTree(patternList, size) - ট্রাই বানানো, ফেইল ফাংশন বিল্ড, আউটপুট লিংক তৈরি

getNextState(presentState, nextChar) - গো-টু/ফেইল ব্যবহার করে নেক্স্ট স্টেট

patternSearch(patternList, size, text) - টেক্সট ট্রাভার্স করে ম্যাচ প্রিন্ট

C++ উদাহরণ

#include <iostream>
#include <queue>
#define MAXS 500
#define MAXC 26
using namespace std;

int output[MAXS], fail[MAXS], gotoMat[MAXS][MAXC];

int buildTree(string arr[], int size) {
    memset(output, 0, sizeof(output));
    memset(fail, -1, sizeof(fail));
    memset(gotoMat, -1, sizeof(gotoMat));
    int state = 1;
    for(int i=0; i

Word there location: 2
Word any location: 7
Word answer location: 10
Word bye location: 22