यह फाइनाइट स्टेट ऑटोमेटन आधारित खोज करने के लिए एक C++ प्रोग्राम है। एक ऑटोमेटन जिसमें राज्यों की एक सीमित संख्या होती है, उसे फाइनाइट ऑटोमेटन कहा जाता है। यहां, एक टेक्स्ट दिया गया है text[0...t-1] और एक पैटर्न p[0...p-1] भी दिया गया है। हमें टेक्स्ट में पैटर्न ढूंढना है और उसकी सभी घटनाओं को संबंधित इंडेक्स पर प्रिंट करना है।
एल्गोरिदम
Begin
Function void transitiontable():
1) पहली पंक्ति में प्रविष्टियां डालें और इसे भरें। पहली पंक्ति में सभी प्रविष्टियां हमेशा 0 होती हैं सिवाय p[0] कैरेक्टर के लिए प्रविष्टि के। p[0] के लिए हमें हमेशा स्टेट 1 पर जाने की आवश्यकता होती है।
2) longestprefixsuffix को 0 के रूप में इनिशियलाइज़ करें।
3) i = 1 से P तक। (यहां P पैटर्न की लंबाई है)
a) इंडेक्स longestprefixsuffix के बराबर पंक्ति से प्रविष्टियां कॉपी करें।
b) p[i] कैरेक्टर के लिए प्रविष्टि को i+1 पर अपडेट करें।
c) longestprefixsuffix = TF[lps][pat[i]] अपडेट करें
जहां TT 2D ऐरे है।
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]]; // TT वह 2D ऐरे है जिसे बनाया जा रहा है
}
}
// टेक्स्ट में पैटर्न की सभी घटनाओं को प्रिंट करता है
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);
return 0;
}
आउटपुट
pattern is found at index: 0 pattern is found at index: 20
फाइनाइट ऑटोमेटन आधारित पैटर्न खोज (KMP एल्गोरिदम से संबंधित) टेक्स्ट को O(n) समय में प्रीप्रोसेस्ड ट्रांजिशन टेबल के साथ प्रोसेस करती है। ट्रांजिशन टेबल बनाने में O(m * अल्फाबेट_साइज) समय लगता है। यह तब कुशल होता है जब एक ही पैटर्न को कई टेक्स्ट्स में खोजा जाता है या जब अल्फाबेट आकार छोटा होता है।