একটি দেওয়া স্ট্রিং থেকে আমরা সব সম্ভাব্য সাফিক্স পেতে পারি। সাফিক্সগুলো লেক্সিকোগ্রাফিক্যালি সর্ট করার পর আমরা সাফিক্স অ্যারে পাই। সাফিক্স অ্যারে সাফিক্স ট্রি ব্যবহার করেও তৈরি করা যায়। সাফিক্স ট্রির DFS ট্রাভার্সেল ব্যবহার করে সাফিক্স অ্যারে পাওয়া যায়। সাফিক্স অ্যারে লিনিয়ার টাইমে সাফিক্স খুঁজে বের করতে সাহায্য করে। আমরা বাইনারি সার্চ টাইপ প্রসিডিউর ব্যবহার করে সাফিক্স অ্যারে দিয়ে সাবস্ট্রিংও খুঁজে পেতে পারি।
টাইম কমপ্লেক্সিটি O(m log n)
ইনপুট এবং আউটপুট
ইনপুট: মেইন স্ট্রিং: "BANANA", প্যাটার্ন: "NAN" আউটপুট: Pattern found at position: 2
অ্যালগরিদম
fillSuffixArray (text, suffArray)
ইনপুট: মেইন স্ট্রিং
আউটপুট: সাফিক্সের অ্যারে
শুরু
n := text দৈর্ঘ্য
allSuffix নামক সাইজ n-এ সাফিক্স অ্যারে ডিফাইন করুন
i := 0 থেকে n-1 পর্যন্ত, করুন
allSuffix[i].index := i
allSuffix[i].suff := text-এর (i থেকে শেষ) সাবস্ট্রিং
শেষ
allSuffix অ্যারে সর্ট করুন
suffArray-তে সকল সাফিক্স অ্যারের ইনডেক্স স্টোর করুন।
শেষ
suffixArraySearch (text, pattern, suffArray)
ইনপুট: মেইন স্ট্রিং, প্যাটার্ন এবং সাফিক্স অ্যারে
আউটপুট - প্যাটার্ন যেখানে পাওয়া গেল সেসব লোকেশন
শুরু
patLen := প্যাটার্নের সাইজ
strLen := টেক্সটের সাইজ
left := 0
right := strLen -1
যতক্ষণ left <= right, করুন
mid := left + (right - left)/2
tempStr := suffArray[mid] থেকে শেষ পর্যন্ত text-এর সাবস্ট্রিং
result := tempStr এবং pattern কে প্যাটার্ন দৈর্ঘ্য পর্যন্ত তুলনা করুন।
যদি result = 0, তবে
লোকেশন প্রিন্ট করুন
যদি res < 0, তবে
right := mid - 1
অন্যথায়
left := mid +1
শেষ
শেষ
উদাহরণ
#include<iostream> #include<algorithm> #include<cstring> using namespace std; struct suffix { int index; string suff; }; int strCompare(string st1, string st2, int n) { int i = 0; while(n--) { if(st1[i] != st2[i]) return st1[i] - st2[i]; i++; } return 0; } bool comp(suffix suff1, suffix suff2) { //সর্টিং এর জন্য দুটি স্ট্রিং তুলনা if(suff1.suff<suff2.suff) return true; return false; } void fillSuffixArray(string mainString, int suffArr[]) { int n = mainString.size(); suffix allSuffix[n]; //সকল সাফিক্স ধারণ করার অ্যারে for(int i = 0; i<n; i++) { allSuffix[i].index = i; allSuffix[i].suff = mainString.substr(i); //i-তম পজিশন থেকে শেষ } sort(allSuffix, allSuffix+n, comp); for(int i = 0; i<n; i++) suffArr[i] = allSuffix[i].index; //সর্টেড সাফিক্সের ইনডেক্স } void suffixArraySearch(string mainString, string pattern, int suffArr[], int array[], int *index) { int patLen = pattern.size(); int strLen = mainString.size(); int left = 0, right = strLen - 1; //বাইনারি সার্চের জন্য left এবং right while(left <= right) { int mid = left + (right - left)/2; string tempStr = mainString.substr(suffArr[mid]); int result = strCompare(pattern,tempStr, patLen); if(result == 0) { //প্যাটার্ন পাওয়া গেল (*index)++; array[(*index)] = suffArr[mid]; } if(result < 0) right = mid -1; else left = mid +1; } } int main() { string mainString = "BANANA"; string pattern = "NAN"; int locArray[mainString.size()]; int index = -1; int suffArr[mainString.size()]; fillSuffixArray(mainString, suffArr); suffixArraySearch(mainString, pattern, suffArr, locArray, &index); for(int i = 0; i <= index; i++) { cout << "Pattern found at position: " << locArray[i]<<endl; } }
আউটপুট
Pattern found at position: 2
