এটি একটি C++ প্রোগ্রাম যা ফাইনাইট স্টেট অটোমেটা (Finite State Automaton) বেসড সার্চ করে। সীমিত সংখ্যক স্টেট (state) বিশিষ্ট অটোমেটাকে ফাইনাইট অটোমেটা বলা হয়। এখানে একটি টেক্সট `text[0...t-1]` এবং একটি প্যাটার্ন `p[0...p-1]` দেওয়া আছে। প্যাটার্নটি টেক্সটে খুঁজে বের করে এর সব অকারের ইনডেক্স প্রিন্ট করতে হবে।
এলগরিদম
Begin
Function void transitiontable():
1) প্রথম রোয়ের এন্ট্রিগুলো দিন এবং ফিল আপ করুন। প্রথম রোয়ের সব এন্ট্রি ০ ছাড়া p[0] ক্যারেক্টারের জন্য। p[0]-এর জন্য সবসময় স্টেট ১-এ যেতে হবে।
2) longestprefixsuffix (lps) ০ দিয়ে ইনিশিয়ালাইজ করুন।
3) for i = 1 to P (P হলো প্যাটার্নের দৈর্ঘ্য)
a) longestprefixsuffix রোয়ের ইনডেক্স থেকে এন্ট্রিগুলো কপি করুন।
b) p[i] ক্যারেক্টারের এন্ট্রি আপডেট করুন i+1 দিয়ে।
c) longestprefixsuffix আপডেট করুন: lps = TT[lps][pat[i]]
যেখানে TT হলো ২ডি অ্যারে।
End
উদাহরণ
#include <iostream>
#include <cstring>
#define NO_OF_CHARS 512
using namespace std;
// দिये गये প্যাটার্নের জন্য ফাইনাইট অটোমেটা রিপ্রেজেন্ট করার TF টেবিল বিল্ড করে
void transitiontable(char *p, int P, int TT[][NO_OF_CHARS]) {
int i, longestprefixsuffix = 0, y;
// প্রথম রোয়ে এন্ট্রি দিন
for (y = 0; y < NO_OF_CHARS; y++)
TT[0][y] = 0;
TT[0][p[0]] = 1;
// অন্যান্য রোয়ে এন্ট্রি দিন
for (i = 1; i <= P; i++) {
// longestprefixsuffix রোয়ের ইনডেক্স থেকে ভ্যালু কপি
for (y = 0; y < NO_OF_CHARS; y++)
TT[i][y] = TT[longestprefixsuffix][y];
// এন্ট্রি আপডেট
TT[i][p[i]] = i + 1;
// পরবর্তী রোয়ের জন্য lps আপডেট
if (i < P)
longestprefixsuffix = TT[longestprefixsuffix][p[i]];
}
}
// টেক্সটে প্যাটার্নের সব অকার প্রিন্ট
void patternsearch(char *p, char *t) {
int P = strlen(p);
int T = strlen(t);
int TT[P+1][NO_OF_CHARS];
transitiontable(p, P, TT);
// FA ওভার টেক্সট প্রসেস
int i, j = 0;
for (i = 0; i < T; i++) {
j = TT[j][t[i]];
if (j == P) {
cout << "\n pattern is found at index: " << i - P + 1;
}
}
}
int main() {
char *text = "AABAA ABBAACCDD CCDDAABAA"; // ইনপুট টেক্সট
char *pattern = "AABAA"; // ইনপুট প্যাটার্ন
patternsearch(pattern, text);
getchar();
return 0;
}
আউটপুট
pattern is found at index: 0 pattern is found at index: 20
