सभी सफिक्स का ट्राई

टेक्स्ट से, हम ट्री संरचना बनाने के लिए सभी सफिक्स उत्पन्न कर सकते हैं। हम जानते हैं कि टेक्स्ट में मौजूद हर पैटर्न, टेक्स्ट में संभावित सफिक्स में से एक का प्रीफिक्स होना चाहिए। सभी सफिक्स का ट्राई बनाकर, हम किसी भी सबस्ट्रिंग को रैखिक समय में ढूंढ सकते हैं। हर सफिक्स स्ट्रिंग टर्मिनेटिंग सिम्बल के साथ समाप्त होता है। प्रत्येक नोड से यदि कोई पथ है, तो यह आगे बढ़ता है, अन्यथा लौटाता है कि पैटर्न नहीं मिला।

इस एल्गोरिदम के लिए, समय जटिलता O(m+k) है, जहां m स्ट्रिंग की लंबाई है और k टेक्स्ट में पैटर्न की फ्रीक्वेंसी है।

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

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

एल्गोरिदम

इस एल्गोरिदम में, हम एक विशेष नोड का उपयोग करेंगे, जिसे ट्राई नोड कहा जाता है। यह सभी सफिक्स के इंडेक्स और दूसरे ट्राई नोड्स के एड्रेस को लिंक के रूप में रखेगा।

createTrie(root: trieNode, text)

इनपुट: trieNode टाइप का एक रूट नोड

आउटपुट: मुख्य स्ट्रिंग का उपयोग करके सफिक्स ट्री

Begin 
  for i := 0 to length of text, do 
    substring from ith position to end as suffix, and add in index i in trie. 
  done 
End

findPat(pattern, node)

इनपुट: खोजने के लिए पैटर्न और नोड, जिसका उपयोग इसके सफिक्स सबट्री में जांच के लिए किया जाता है

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

Begin 
  if pattern size is 0, then 
    return suffIndex of node 
  if node.suff[patten[0]] ≠ φ, then 
    return node.suff[pattern[0]].findPat(substring from 1 to end of pattern) 
  else 
    return φ 
End

searchPat(pattern)

इनपुट - वह पैटर्न जिसे खोजा जाएगा

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

Begin 
  define res as list. 
  res := findPat(pattern) 
  if res ≠ φ, then 
    patLen := length of pattern 
    for i := 0 to end of res list, do 
      print all indexes where pattern was found 
    done 
End

उदाहरण

#include<iostream> #include<list> #define MAXCHAR 256 using namespace std; class trieNode { //node to hold all suffixes private: trieNode *suff[MAXCHAR]; list *suffIndex; public: trieNode() { suffIndex = new list(); for (int i = 0; i < MAXCHAR; i++) suff[i] = NULL; //no child initially } void addSuffix(string suffix, int sIndex); list* searchPattern(string pat); }; void trieNode::addSuffix(string suffix, int sIndex) { suffIndex->push_back(sIndex); //store index initially if (suffix.size() > 0) { char cIndex = suffix[0]; if (suff[cIndex] == NULL) //if no sub tree present for this character suff[cIndex] = new trieNode(); //create new node suff[cIndex]->addSuffix(suffix.substr(1), sIndex+1); //for next suffix } } list* trieNode::searchPattern(string pattern) { if (pattern.size() == 0) return suffIndex; if (suff[pattern[0]] != NULL) return (suff[pattern[0]])->searchPattern(pattern.substr(1)); //follow to next node else return NULL; //when no node are there to jump } class trieSuffix { //trie for all suffixes trieNode root; public: trieSuffix(string mainString) { //add suffixes and make trie for (int i = 0; i < mainString.length(); i++) root.addSuffix(mainString.substr(i), i); } void searchPat(string pattern, int *locArray, int *index); }; void trieSuffix::searchPat(string pattern, int *locArray, int *index) { list *res = root.searchPattern(pattern); // Check if the list of indexes is empty or not if (res != NULL) { list::iterator it; int patLen = pattern.length(); for (it = res->begin(); it != res->end(); it++) { (*index)++; locArray[(*index)] = *it - patLen; } } } int main() { string mainString = "ABAAABCDBBABCDDEBCABC"; string pattern = "ABC"; int locArray[mainString.size()]; int index = -1; trieSuffix trie(mainString); trie.searchPat(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