कसाई का एल्गोरिदम

कसाई का एल्गोरिदम सफिक्स ऐरे से लॉन्गेस्ट कॉमन प्रीफिक्स (LCP) ऐरे प्राप्त करने के लिए उपयोग किया जाता है। सबसे पहले सफिक्स ऐरे ढूंढे जाते हैं। उसके बाद कसाई का एल्गोरिदम LCP ढूंढने के लिए सफिक्स ऐरे सूची लेता है।

LCP ऐरे के लिए, यह O(m log n) लेता है, जहां m पैटर्न की लंबाई है और n टेक्स्ट की लंबाई है। कसाई के एल्गोरिदम के लिए, यह मुख्य स्ट्रिंग में पैटर्न खोजने के लिए O(n) लेता है।

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

इनपुट: मुख्य स्ट्रिंग: "banana" आउटपुट: सफिक्स ऐरे: 5 3 1 0 4 2 कॉमन प्रीफिक्स ऐरे: 1 3 0 0 2 0

एल्गोरिदम

buildSuffixArray(text)

इनपुट: मुख्य स्ट्रिंग

आउटपुट: मुख्य टेक्स्ट से बना सफिक्स ऐरे

Begin 
  n := size of text 
  for i := 0 to n, do 
    suffArray[i].index := i 
    suffArray[i].rank[0] := text[i] 
    if (i+1) < n, then 
      suffArray[i].rank[1] := text[i+1] 
    else 
      suffArray[i].rank[1] := -1 
  do 
    sort the suffix array 
    define index array to store indexes 
    for k := 4 to (2*n)-1, increase k by k*2, do 
      currRank := 0 
      prevRank := suffArray[0].rank[0] 
      suffArray[0].rank[0] := currRank 
      index[suffArray[0].index] = 0 
      for all character index i of text, do 
        if suffArray[i].rank[0] = prevRank AND suffArray[i].rank[1] = suffArray[i-1].rank[1], then 
          prevRank := suffArray[i].rank[0] 
          suffArray[i].rank[0] := currRank 
        else 
          prevRank := suffArray[i].rank[0] 
          suffArray[i].rank[0] := currRank + 1 
          currRank := currRank + 1 
          index[suffArray[i].index] := i 
      done 
      for all character index i of text, do 
        nextIndex := suffArray[i].index + k/2 
        if nextIndex < n, then 
          suffArray[i].rank[1] := suffArray[index[nextIndex]].rank[0] 
        else 
          suffArray[i].rank[1] := -1 
      done 
      sort the suffArray 
    done 
    for all character index i of text, do 
      insert suffArray[i].index into suffVector 
    done 
End

kasaiAlgorithm(text, suffVector)

इनपुट - मुख्य टेक्स्ट, और सफिक्स वेक्टर सफिक्स की सूची के रूप में

आउटपुट: वह स्थान जहां लॉन्गेस्ट कॉमन प्रीफिक्स मिला

Begin 
  n := size of suffVector 
  define longPrefix list of size n and fill all entries with 0 
  define suffInverse list of size n and fill all entries with 0 
  for all index values 'i' of suffVector, do 
    suffInverse[suffVector[i]] = i 
  done 
  k := 0 
  for i := 0 to n-1, do 
    if suffInverse[i] = n-1 then 
      k :=0 
      ignore the bottom part and go for next iteration. 
    j := suffVector[suffInverse[i]+1] 
    while (i+k) 0 then 
      decrease k by 1 
  done 
  return longPrefix 
End

उदाहरण

#include<iostream> #include<vector> #include<algorithm> using namespace std; struct suffix { int index; int rank[2]; // To store rank pair }; bool compare(suffix s1, suffix s2) { //compare suffixes for sort function 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 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'; //store old rank suffixArray[i].rank[1] = ((i+1)suffixVector; for (int i = 0; i < n; i++) suffixVector.push_back(suffixArray[i].index); //index of all suffix to suffix vector return suffixVector; } vector kasaiAlgorithm(string mainString, vector suffixVector) { int n = suffixVector.size(); vector longPrefix(n, 0); //size n and initialize with 0 vector suffixInverse(n, 0); for (int i=0; i < n; i++) suffixInverse[suffixVector[i]] = i; //fill values of inverse Suffix list int k = 0; for (int i=0; i0) k--; //remofe first character of string } return longPrefix; } void showArray(vector vec) { vector::iterator it; for (it = vec.begin(); it < vec.end() ; it++) cout << *it << " "; cout << endl; } int main() { string mainString = "banana"; vectorsuffixArray = buildSuffixArray(mainString); int n = suffixArray.size(); cout<< "Suffix Array : "<commonPrefix = kasaiAlgorithm(mainString, suffixArray); cout<< "\nCommon Prefix Array : "<

आउटपुट
Suffix Array : 5 3 1 0 4 2 Common Prefix Array : 1 3 0 0 2 0