C++ প্রোগ্রাম: ফাইনাইট অটোমেটা অ্যালগরিদম প্যাটার্ন সার্চিংয়ের জন্য

ফাইনাইট অটোমেটা (Finite Automata) প্যাটার্ন সার্চিংয়ের জন্য একটি স্টেট মেশিন বানায়। প্রি-প্রসেসিং-এ ২D ট্রানজিশন টেবিল তৈরি করা হয়, এরপর টেক্সট ট্রাভার্স করে প্যাটার্ন ম্যাচ করা হয়।

অ্যালগরিদম

1. TF[state][char] = পরের স্টেট (প্রি-কম্পিউটেড)।
2. স্টেট ০ থেকে শুরু করে টেক্সট পড়ুন।
3. স্টেট M (প্যাটার্ন দৈর্ঘ্য) হলে ম্যাচ পাওয়া গেল।

C++ কোড উদাহরণ

#include <stdio.h>
#include <string.h>
#define CHARS 256

int nextState(char *pat, int M, int state, int x) {
    if (state < M && x == pat[state]) return state+1;
    for (int ns=state; ns>0; ns--) {
        if (pat[ns-1] == x) {
            int i; for (i=0; i

আউটপুট
Pattern found at index 11
Pattern found at index 22