ফাইনাইট অটোমেটা কার্যকর কনস্ট্রাকশন

ফাইনাইট অটোমেটা কনস্ট্রাক্ট করে টেক্সটে প্যাটার্ন সার্চিং সহজে করা যায়। প্রথমে একটি ২ডি অ্যারে ফিল করতে হয় ফাইনাইট অটোমেটার ট্রানজিশন টেবিল বানাতে। একবার টেবিল তৈরি হলে, সার্চিং প্রসিডিউর সহজ। অটোমেটার প্রথম স্টেট থেকে শুরু করে, যখন ফাইনাল স্টেটে পৌঁছায়, মানে প্যাটার্ন স্ট্রিং-এ পাওয়া গেল।

ফাইনাইট অটোমেটা কনস্ট্রাকশনের টাইম কমপ্লেক্সিটি O(M*K), M হলো প্যাটার্ন দৈর্ঘ্য এবং K হলো ভিন্ন ক্যারেক্টার সংখ্যা। মেইন প্যাটার্ন সার্চিং কমপ্লেক্সিটি O(n)।

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

ইনপুট: মেইন স্ট্রিং: "ABAAABCDBBABCDDEBCABC", প্যাটার্ন "ABC" আউটপুট: Pattern found at position: 4 Pattern found at position: 10 Pattern found at position: 18

অ্যালগরিদম

fillTransTable(pattern, transTable)

ইনপুট - প্যাটার্ন এবং ট্রানজিশন টেবিল যেটি ট্রানজিশন দিয়ে ফিল করতে হবে

আউটপুট - ভরা हुआ ট্রানজিশন টেবিল

শুরু
  longPS := 0
  ট্রানজিশন টেবিলের সব এন্ট্রি ০ দিয়ে ক্লিয়ার করুন
  transTable[0, patter[0]] = 1 //প্যাটার্নের প্রথম ক্যারেক্টারের জন্য
  প্যাটার্নে উপস্থিত সব ক্যারেক্টারের ইনডেক্স i-এর জন্য করুন
    সব সম্ভাব্য ক্যারেক্টারের জন্য করুন
      transTable[i,j] := transTable[longPS, j]
    শেষ
    transTable[i, pattern[i]] := i+1
    যদি i < প্যাটার্ন সাইজ, তবে
      longPS := transTable[longPS, pattern[i]]
  শেষ
শেষ

patternSearch(text, pattern)

ইনপুট - মেইন টেক্সট এবং প্যাটার্ন

আউটপুট - ইনডেক্স, যেখানে প্যাটার্ন পাওয়া গেল।

শুরু
  patLen := প্যাটার্ন দৈর্ঘ্য
  strLen := স্ট্রিং দৈর্ঘ্য
  fillTransTable(pattern, transTable) কল করুন
  present := 0
  টেক্সটের সব ক্যারেক্টারের ইনডেক্স i-এর জন্য করুন
    present := transTable[present, text[i]]
    যদি present = patLen, তবে
      লোকেশন (i - patLen +1) প্রিন্ট করুন কারণ সেখানে প্যাটার্ন আছে
  শেষ
শেষ

উদাহরণ

#include<iostream> #define MAXCHAR 256 using namespace std; void fillTransitionTable(string pattern, int transTable[][MAXCHAR]) { int longPS = 0; for (int i = 0; i < MAXCHAR; i++) { transTable[0][i] = 0; //প্রথম স্টেটের এন্ট্রি তৈরি করুন } transTable[0][pattern[0]] = 1; //প্রথম ক্যারেক্টারের জন্য প্রথম স্টেটে যান for (int i = 1; i<= pattern.size(); i++) { for (int j = 0; j < MAXCHAR ; j++) //প্রিফিক্স এবং সাফিক্স ব্যবহার করে স্টেট আপডেট করুন transTable[i][j] = transTable[longPS][j]; transTable[i][pattern[i]] = i + 1; if (i < pattern.size()) longPS = transTable[longPS][pattern[i]]; //নেক্সট স্টেটের জন্য লংগেস্ট প্রিফিক্স এবং সাফিক্স আপডেট করুন } } void FAPatternSearch(string mainString, string pattern, int array[], int *index) { int patLen = pattern.size(); int strLen = mainString.size(); int transTable[patLen+1][MAXCHAR]; //প্রতিটি প্যাটার্নের জন্য ট্রানজিশন টেবিল তৈরি করুন fillTransitionTable(pattern, transTable); int presentState = 0; for(int i = 0; i<=strLen; i++) { presentState = transTable[presentState][mainString[i]]; //ট্রানজিশন সম্ভব হলে নেক্সট স্টেটে যান if(presentState == patLen) { //যখন প্রেজেন্ট স্টেট ফাইনাল স্টেট, প্যাটার্ন পাওয়া গেল (*index)++; array[(*index)] = i - patLen + 1 ; } } } int main() { string mainString = "ABAAABCDBBABCDDEBCABC"; string pattern = "ABC"; int locArray[mainString.size()]; int index = -1; FAPatternSearch(mainString, pattern, locArray, &index); for(int i = 0; i <= index; i++) { cout << "Pattern found at position: " << locArray[i]<<endl; } }

আউটপুট

Pattern found at position: 4 Pattern found at position: 10 Pattern found at position: 18