इस लेख में, हम पैटर्न खोज के लिए फाइनाइट ऑटोमेटा एल्गोरिदम को निष्पादित करने के लिए एक प्रोग्राम पर चर्चा करेंगे।
हमें एक टेक्स्ट[0...n-1] और एक पैटर्न[0...m-1] प्रदान किया गया है। हमें पैटर्न[] की टेक्स्ट[] में सभी घटनाओं को खोजना होगा।
इसके लिए हम टेक्स्ट[] को पूर्व-प्रसंस्कृत करेंगे और इसे दर्शाने के लिए एक 2-D एरे बनाएंगे। उसके बाद हमें बस टेक्स्ट[] के तत्वों और ऑटोमेटा की विभिन्न अवस्थाओं के बीच पार करना होगा।
उदाहरण
#include <stdio.h>
#include <string.h>
#define total_chars 256
int calc_nextstate(char *pat, int M, int state, int x) {
if (state < M && x == pat[state])
return state+1;
int ns, i;
for (ns = state; ns > 0; ns--) {
if (pat[ns-1] == x) {
for (i = 0; i < ns-1; i++)
if (pat[i] != pat[state-ns+1+i])
break;
if (i == ns-1)
return ns;
}
}
return 0;
}
// फाइनाइट ऑटोमेटा बनाता है
void calc_TF(char *pat, int M, int TF[][total_chars]) {
int state, x;
for (state = 0; state <= M; ++state)
for (x = 0; x < total_chars; ++x)
TF[state][x] = calc_nextstate(pat, M, state, x);
}
// टेक्स्ट में पैटर्न की सभी घटनाओं को प्रिंट करता है
void calc_occur(char *pat, char *txt) {
int M = strlen(pat);
int N = strlen(txt);
int TF[M+1][total_chars];
calc_TF(pat, M, TF);
int i, state = 0;
for (i = 0; i < N; i++) {
state = TF[state][txt[i]];
if (state == M)
printf("\n Given pattern is found at the index %d", i-M+1);
}
}
int main() {
char *txt = "AABCDAABBDCAABADAABDABAABA";
char *pat = "AABA";
calc_occur(pat, txt);
return 0;
}
आउटपुट
Given pattern is found at the index 11 Given pattern is found at the index 22
