फाइनाइट ऑटोमेटा का कुशल निर्माण

फाइनाइट ऑटोमेटा का निर्माण करके, हम टेक्स्ट में पैटर्न खोज को सरलता से कर सकते हैं। सबसे पहले, हमें फाइनाइट ऑटोमेटा की ट्रांजिशन टेबल बनाने के लिए एक 2D ऐरे भरना होगा। एक बार टेबल बन जाने के बाद, खोज प्रक्रिया सरल है। ऑटोमेटा के पहले स्टेट से शुरू करके, जब हम फाइनल स्टेट पर पहुंचते हैं, तो इसका मतलब है कि पैटर्न स्ट्रिंग में मिल गया है।

फाइनाइट ऑटोमेटा निर्माण के लिए, समय जटिलता O(M*K) है, M पैटर्न की लंबाई है और K अलग-अलग कैरेक्टर की संख्या है। मुख्य पैटर्न खोज की जटिलता O(n) है।

इनपुट और आउटपुट

इनपुट: मुख्य स्ट्रिंग: "ABAAABCDBBABCDDEBCABC", पैटर्न "ABC" आउटपुट: पैटर्न स्थान पर मिला: 4 पैटर्न स्थान पर मिला: 10 पैटर्न स्थान पर मिला: 18

एल्गोरिदम

fillTransTable(pattern, transTable)

इनपुट - पैटर्न और ट्रांजिशन टेबल जिसे ट्रांजिशन के साथ भरना है

आउटपुट - भरी हुई ट्रांजिशन टेबल

Begin 
  longPS := 0 
  clear all entries of transition table with 0 
  transTable[0, patter[0]] = 1 //for the first character of the pattern 
  for index of all character i present in pattern, do 
    for all possible characters, do 
      transTable[i,j] := transTable[longPS, j] 
    done 
    transTable[i, pattern[i]] := i+1 
    if i < pattern size, then 
      longPS := transTable[longPS, pattern[i]] 
  done 
End

patternSearch(text, pattern)

इनपुट - मुख्य टेक्स्ट और पैटर्न

आउटपुट - वह इंडेक्स, जहां पैटर्न मिले

Begin 
  patLen := pattern length 
  strLen := string length 
  call fillTransTable(pattern, transTable) 
  present := 0 
  for all character's index i of text, do 
    present := transTable[present, text[i]] 
    if present = patLen, then 
      print the location (i – patLen +1) as there is the pattern 
  done 
End

उदाहरण

#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; // create entries for first state } transTable[0][pattern[0]] = 1; //move to first state for first character for (int i = 1; i<= pattern.size(); i++) { for (int j = 0; j < MAXCHAR ; j++) // update states using prefix and suffix transTable[i][j] = transTable[longPS][j]; transTable[i][pattern[i]] = i + 1; if (i < pattern.size()) longPS = transTable[longPS][pattern[i]]; //update longest prefix and suffix for next states } } void FAPatternSearch(string mainString, string pattern, int array[], int *index) { int patLen = pattern.size(); int strLen = mainString.size(); int transTable[patLen+1][MAXCHAR]; //create transition table for each pattern fillTransitionTable(pattern, transTable); int presentState = 0; for(int i = 0; i<=strLen; i++) { presentState = transTable[presentState][mainString[i]]; //move to next state is transition is possible if(presentState == patLen) { //when present state is the final state, pattern found (*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]<

आउटपुट
Pattern found at position: 4 Pattern found at position: 10 Pattern found at position: 18