সমস্ত প্রত্যয় চেষ্টা করুন

পাঠ্য থেকে, আমরা একটি গাছের গঠন তৈরি করতে সমস্ত প্রত্যয় তৈরি করতে পারি। আমরা জানি যে প্রতিটি প্যাটার্ন যা পাঠ্যে উপস্থাপন করে, পাঠ্যের সম্ভাব্য প্রত্যয়গুলির একটির একটি উপসর্গ হতে হবে। সমস্ত প্রত্যয়ের Trie তৈরি করে, আমরা রৈখিক সময়ে যেকোনো সাবস্ট্রিং খুঁজে পেতে পারি। প্রতিটি প্রত্যয় স্ট্রিং টার্মিনেটিং চিহ্ন দিয়ে শেষ হয়। প্রতিটি নোড থেকে যদি কোন পথ থাকে, এটি এগিয়ে যায়, অন্যথায় সেই প্যাটার্নটি পাওয়া যায় না।

এই অ্যালগরিদমের জন্য, সময়ের জটিলতা হল O(m+k), যেখানে m হল স্ট্রিংয়ের দৈর্ঘ্য এবং k হল টেক্সটের প্যাটার্নের ফ্রিকোয়েন্সি।

ইনপুট এবং আউটপুট

Input:
Main String: “ABAAABCDBBABCDDEBCABC”. Pattern “ABC”
Output:
Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 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 tire.
   done
End

ফাইন্ডপ্যাট(প্যাটার্ন, নোড)

ইনপুট: খুঁজে পেতে প্যাটার্ন এবং নোড, যা এর প্রত্যয় সাবট্রিগুলি চেক করতে ব্যবহৃত হয়

আউটপুট - সূচী তালিকা যেখানে প্যাটার্নটি পাওয়া গেছে

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 o pattern)
   else
      return φ
End

সার্চপ্যাট(প্যাটার্ন)

ইনপুট - যে প্যাটার্নটি অনুসন্ধান করা হবে

আউটপুট - তালিকা যেখানে পাঠ্যের সূচী, যেখানে প্যাটার্ন পাওয়া গেছে

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<int> *suffIndex;
   public:
      trieNode() {
         suffIndex = new list<int>;
         for (int i = 0; i < MAXCHAR; i++)
            suff[i] = NULL;       //no child initially
      }

      void addSuffix(string suffix, int sIndex);
      list<int>* 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<int>* 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<int> *res = root.searchPattern(pattern);
   // Check if the list of indexes is empty or not
   if (res != NULL) {
      list<int>::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]<<endl;
   }

}

আউটপুট

Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18