টেক্সট থেকে আমরা সব সাফিক্স জেনারেট করে একটি ট্রি স্ট্রাকচার बनाয়। আমরা জানি, টেক্সটে যে কোনো প্যাটার্ন থাকলে, সেটি টেক্সটের সম্ভাব্য সাফিক্সগুলোর একটির প্রিফিক্স হয় অবশ্যই। সব সাফিক্সের ট্রাই বিল্ড করে আমরা লিনিয়ার টাইমে যেকোনো সাবস্ট্রিং খুঁজে পেতে পারি। প্রতিটি সাফিক্স স্ট্রিং টার্মিনেটিং সিম্বল দিয়ে শেষ হয়। প্রতিটি নোড থেকে যদি কোনো পথ থাকে, তবে সেটি ফরওয়ার্ড হয়, অন্যথায় রিটার্ন করে যে প্যাটার্নটি খুঁজে পাওয়া যায়নি।
এই অ্যালগরিদমের টাইম কমপ্লেক্সিটি O(m+k), যেখানে m হলো স্ট্রিংয়ের দৈর্ঘ্য এবং k হলো টেক্সটে প্যাটার্নের ফ্রিকোয়েন্সি।
ইনপুট এবং আউটপুট
ইনপুট: মেইন স্ট্রিং: "ABAAABCDBBABCDDEBCABC"। প্যাটার্ন "ABC" আউটপুট: Pattern found at position: 4 Pattern found at position: 10 Pattern found at position: 18
অ্যালগরিদম
এই অ্যালগরিদমে, আমরা একটি স্পেশাল নোড ব্যবহার করব, যাকে ট্রাই নোড বলে। এটি সব সাফিক্সের ইনডেক্স এবং অন্য ট্রাই নোডের অ্যাড্রেস লিঙ্ক হিসেবে রাখবে।
createTrie(root: trieNode, text)
ইনপুট: trieNode টাইপের একটি রুট নোড।
আউটপুট: মেইন স্ট্রিং ব্যবহার করে সাফিক্স ট্রি
শুরু
i := 0 থেকে text-এর দৈর্ঘ্য পর্যন্ত, করুন
i-তম পজিশন থেকে শেষ পর্যন্ত সাবস্ট্রিং হিসেবে সাফিক্স, এবং i ইনডেক্স ট্রাই-তে যোগ করুন।
শেষ
শেষ
findPat(pattern, node)
ইনপুট: খুঁজতে হবে প্যাটার্ন এবং নোড, যেটি তার সাফিক্স সাবট্রিতে চেক করতে ব্যবহৃত হয়
আউটপুট - যে ইনডেক্স লিস্টে প্যাটার্নটি পাওয়া গেল
শুরু
যদি প্যাটার্ন সাইজ 0 হয়, তবে
node-এর suffIndex রিটার্ন করুন
যদি node.suff[patten[0]] ≠ φ, তবে
return node.suff[pattern[0]].findPat(প্যাটার্নের 1 থেকে শেষ পর্যন্ত সাবস্ট্রিং)
অন্যথায়
return φ
শেষ
searchPat(pattern)
ইনপুট - সার্চ করা প্যাটার্ন
আউটপুট - টেক্সটের সেই ইনডেক্সের লিস্ট যেখানে প্যাটার্নটি পাওয়া গেল
শুরু
res কে লিস্ট হিসেবে ডিফাইন করুন।
res := findPat(pattern)
যদি res ≠ φ, তবে
patLen := প্যাটার্নের দৈর্ঘ্য
i := 0 থেকে res লিস্টের শেষ পর্যন্ত, করুন
প্যাটার্ন যেখানে পাওয়া গেল সেসব ইনডেক্স প্রিন্ট করুন
শেষ
শেষ
উদাহরণ
#include<iostream> #include<list> #define MAXCHAR 256 using namespace std; class trieNode { //সকল সাফিক্স ধারণ করার নোড private: trieNode *suff[MAXCHAR]; list<int> *suffIndex; public: trieNode() { suffIndex = new list<int>(); for (int i = 0; i < MAXCHAR; i++) suff[i] = NULL; //প্রাথমিকভাবে কোনো চাইল্ড নেই } void addSuffix(string suffix, int sIndex); list<int>* searchPattern(string pat); }; void trieNode::addSuffix(string suffix, int sIndex) { suffIndex->push_back(sIndex); //প্রাথমিকভাবে ইনডেক্স স্টোর করুন if (suffix.size() > 0) { char cIndex = suffix[0]; if (suff[cIndex] == NULL) //যদি এই ক্যারেক্টারের জন্য কোনো সাব ট্রি নেই থাকে suff[cIndex] = new trieNode(); //নতুন নোড তৈরি করুন suff[cIndex]->addSuffix(suffix.substr(1), sIndex+1); //পরবর্তী সাফিক্সের জন্য } } 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)); //পরবর্তী নোডে যান else return NULL; //যদি কোনো নোড নেই куда যেতে } class trieSuffix { //সকল সাফিক্সের ট্রাই trieNode root; public: trieSuffix(string mainString) { //সাফিক্স যোগ করুন এবং ট্রাই তৈরি করুন 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); // ইনডেক্সের লিস্ট খালি কিনা চেক করুন 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
