কাসাই'স অ্যালগরিদম

কাসাই'স অ্যালগরিদম সাফিক্স অ্যারে থেকে লংগেস্ট কমন প্রিফিক্স (LCP) অ্যারে বের করার জন্য ব্যবহৃত হয়। প্রথমে সাফিক্স অ্যারেগুলো বের করা হয়। তারপর কাসাই'স অ্যালগরিদম সাফিক্স অ্যারে লিস্ট নেয় LCP বের করতে।

LCP অ্যারেতে O(m log n) লাগে, যেখানে m হলো প্যাটার্ন দৈর্ঘ্য এবং n হলো টেক্সটের দৈর্ঘ্য। কাসাই'স অ্যালগরিদমে, মেইন স্ট্রিং-এ প্যাটার্ন সার্চ করার জন্য O(n) লাগে।

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

ইনপুট: মেইন স্ট্রিং: "banana" আউটপুট: Suffix Array : 5 3 1 0 4 2 Common Prefix Array : 1 3 0 0 2 0

অ্যালগরিদম

buildSuffixArray(text)

ইনপুট: মেইন স্ট্রিং

আউটপুট: মেইন টেক্সট থেকে বিল্ট সাফিক্স অ্যারে

শুরু
  n := text সাইজ
  i := 0 থেকে n পর্যন্ত, করুন
    suffArray[i].index := i
    suffArray[i].rank[0] := text[i]
    যদি (i+1) < n, তবে
      suffArray[i].rank[1] := text[i+1]
    অন্যথায়
      suffArray[i].rank[1] := -1
  করুন
    সাফিক্স অ্যারে সর্ট করুন
    ইনডেক্স স্টোর করার জন্য ইনডেক্স অ্যারে ডিফাইন করুন
    k := 4 থেকে (2*n)-1 পর্যন্ত, k = k*2 করে বাড়ান, করুন
      currRank := 0
      prevRank := suffArray[0].rank[0]
      suffArray[0].rank[0] := currRank
      index[suffArray[0].index] = 0
      টেক্সটের সব ক্যারেক্টার ইনডেক্স i-এর জন্য করুন
        যদি suffArray[i].rank[0] = prevRank AND suffArray[i].rank[1] = suffArray[i-1].rank[1], তবে
          prevRank := suffArray[i].rank[0]
          suffArray[i].rank[0] := currRank
        অন্যথায়
          prevRank := suffArray[i].rank[0]
          suffArray[i].rank[0] := currRank + 1
          currRank := currRank + 1
          index[suffArray[i].index] := i
      শেষ
      টেক্সটের সব ক্যারেক্টার ইনডেক্স i-এর জন্য করুন
        nextIndex := suffArray[i].index + k/2
        যদি nextIndex < n, তবে
          suffArray[i].rank[1] := suffArray[index[nextIndex]].rank[0]
        অন্যথায়
          suffArray[i].rank[1] := -1
      শেষ
      suffArray সর্ট করুন
  শেষ
  টেক্সটের সব ক্যারেক্টার ইনডেক্স i-এর জন্য করুন
    suffArray[i].index suffVector-এ ইনসার্ট করুন
  শেষ
শেষ

kasaiAlgorithm(text, suffVector)

ইনপুট - মেইন টেক্সট, এবং সাফিক্স ভেক্টর যেটি সাফিক্সের লিস্ট

আউটপুট: লংগেস্ট কমন প্রিফিক্স কোথায় পাওয়া গেল সেসব লোকেশন

শুরু
  n := suffVector সাইজ
  longPrefix লিস্ট সাইজ n দিয়ে ডিফাইন করুন এবং সব এন্ট্রি 0 দিয়ে ফিল করুন
  suffInverse লিস্ট সাইজ n দিয়ে ডিফাইন করুন এবং সব এন্ট্রি 0 দিয়ে ফিল করুন
  suffVector-এর সব ইনডেক্স ভ্যালু 'i'-এর জন্য করুন
    suffInverse[suffVector[i]] = i
  শেষ
  k := 0
  i := 0 থেকে n-1 পর্যন্ত, করুন
    যদি suffInverse[i] = n-1 হয়, তবে
      k :=0
      বটম পার্ট ইগনোর করুন এবং নেক্সট ইটারেশনের জন্য যান।
    j := suffVector[suffInverse[i]+1]
    যতক্ষণ (i+k) 0 হয়, তবে
      k 1 কমান
  শেষ
  longPrefix রিটার্ন করুন
শেষ

উদাহরণ

#include<iostream> #include<vector> #include<algorithm> using namespace std; struct suffix { int index; int rank[2]; // র‍্যাঙ্ক পেয়ার স্টোর করতে }; bool compare(suffix s1, suffix s2) { //সর্ট ফাংশনের জন্য সাফিক্স তুলনা if(s1.rank[0] == s2.rank[0]) { if(s1.rank[1] < s2.rank[1]) return true; else return false; }else { if(s1.rank[0] < s2.rank[0]) return true; else return false; } } vector<int> buildSuffixArray(string mainString) { int n = mainString.size(); suffix suffixArray[n]; for (int i = 0; i < n; i++) { suffixArray[i].index = i; suffixArray[i].rank[0] = mainString[i] - 'a'; //পুরনো র‍্যাঙ্ক স্টোর করুন suffixArray[i].rank[1] = ((i+1)<n)?(mainString[i+1]-'a'):-1; //আলফাবেটিক্যাল অর্ডারিং এর পর র‍্যাঙ্ক } sort(suffixArray, suffixArray+n, compare); //প্রথম ২ ক্যারেক্টর পর্যন্ত সাফিক্স অ্যারে সর্ট করুন int index[n]; //সাফিক্স অ্যারেতে ইনডেক্স for (int k = 4; k < 2*n; k = k*2) { //k কে ২-এর ঘাত হিসেবে বাড়ান int currRank = 0; int prevRank = suffixArray[0].rank[0]; suffixArray[0].rank[0] = currRank; index[suffixArray[0].index] = 0; for (int i = 1; i < n; i++) { //সকল সাফিক্সের র‍্যাঙ্ক অ্যাসাইন করুন if (suffixArray[i].rank[0] == prevRank && suffixArray[i].rank[1] == suffixArray[i-1].rank[1]) { prevRank = suffixArray[i].rank[0]; suffixArray[i].rank[0] = currRank; } else{ //র‍্যাঙ্ক ইনক্রিমেন্ট করুন এবং অ্যাসাইন করুন prevRank = suffixArray[i].rank[0]; suffixArray[i].rank[0] = ++currRank; } index[suffixArray[i].index] = i; } for (int i = 0; i < n; i++) { //প্রতিটি সাফিক্সের নেক্সট র‍্যাঙ্ক অ্যাসাইন করুন int nextIndex = suffixArray[i].index + k/2; suffixArray[i].rank[1] = (nextIndex < n)? suffixArray[index[nextIndex]].rank[0]: -1; } sort(suffixArray, suffixArray+n, compare); //প্রথম k ক্যারেক্টর পর্যন্ত সর্ট করুন } vector<int>suffixVector; for (int i = 0; i < n; i++) suffixVector.push_back(suffixArray[i].index); //সকল সাফিক্সের ইনডেক্স সাফিক্স ভেক্টরে return suffixVector; } vector<int> kasaiAlgorithm(string mainString, vector<int> suffixVector) { int n = suffixVector.size(); vector<int> longPrefix(n, 0); //সাইজ n এবং ০ দিয়ে ইনিশিয়ালাইজ vector<int> suffixInverse(n, 0); for (int i=0; i < n; i++) suffixInverse[suffixVector[i]] = i; //ইনভার্স সাফিক্স লিস্টের ভ্যালু ফিল করুন int k = 0; for (int i=0; i<n; i++) { //মেইন স্ট্রিংয়ের সব সাফিক্সের জন্য if (suffixInverse[i] == n-1) { //যখন সাফিক্স (n-1) পজিশনে থাকে k = 0; continue; } int j = suffixVector[suffixInverse[i]+1]; //সাফিক্স লিস্টের নেস্ট স্ট্রিং while (i+k<n && j+k<n && mainString[i+k]==mainString[j+k]) //k-তম ইনডেক্স থেকে শুরু k++; longPrefix[suffixInverse[i]] = k; //কারেন্ট সাফিক্সের জন্য প্রিফিক্স। if (k>0) k--; //স্ট্রিংয়ের প্রথম ক্যারেক্টার রিমুভ করুন } return longPrefix; } void showArray(vector<int> vec) { vector<int>::iterator it; for (it = vec.begin(); it < vec.end() ; it++) cout << *it << " "; cout << endl; } int main() { string mainString = "banana"; vector<int>suffixArray = buildSuffixArray(mainString); int n = suffixArray.size(); cout<< "Suffix Array : " <<endl; showArray(suffixArray); vector<int>commonPrefix = kasaiAlgorithm(mainString, suffixArray); cout<< "\nCommon Prefix Array : " <<endl; showArray(commonPrefix); }

আউটপুট

Suffix Array : 5 3 1 0 4 2 Common Prefix Array : 1 3 0 0 2 0