सफिक्स ऐरे

एक दी गई स्ट्रिंग से, हम सभी संभावित सफिक्स प्राप्त कर सकते हैं। सफिक्स को लेक्सिकोग्राफिकल क्रम में सॉर्ट करने के बाद, हम सफिक्स ऐरे प्राप्त कर सकते हैं। सफिक्स ऐरे को सफिक्स ट्री का उपयोग करके भी बनाया जा सकता है। सफिक्स ट्री के DFS ट्रैवर्सल का उपयोग करके, हम सफिक्स ऐरे प्राप्त कर सकते हैं। सफिक्स ऐरे रैखिक समय में सफिक्स ढूंढने में सहायक होते हैं। हम बाइनरी सर्च प्रकार की प्रक्रिया का उपयोग करके सफिक्स ऐरे से सबस्ट्रिंग भी ढूंढ सकते हैं।

समय जटिलता O(m log n) है

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

इनपुट: मुख्य स्ट्रिंग: "BANANA", पैटर्न: "NAN" आउटपुट: पैटर्न स्थान पर मिला: 2

एल्गोरिदम

fillSuffixArray (text, suffArray)

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

आउटपुट: सफिक्स का ऐरे

Begin 
  n := text Length 
  define suffix array as allSuffix of size n 
  for i := 0 to n-1, do 
    allSuffix[i].index := i 
    allSuffix[i].suff := substring of text from (i to end) 
  done 
  sort the allSuffix array 
  store indexes of all suffix array in suffArray. 
End

suffixArraySearch (text, pattern, suffArray)

इनपुट: मुख्य स्ट्रिंग, पैटर्न और सफिक्स ऐरे

आउटपुट - वह स्थान जहां पैटर्न मिले

Begin 
  patLen := size of pattern 
  strLen := size of text 
  left := 0 
  right := strLen -1 
  while left <= right, do 
    mid := left + (right - left)/2 
    tempStr := substring of text from suffArray[mid] to end 
    result := compare tempStr and pattern upto pattern length. 
    if result = 0, then 
      print the location 
    if res < 0, then 
      right := mid – 1 
    else 
      left := mid +1 
  done 
End

उदाहरण

#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) { //compare two strings for sorting if(suff1.suff

आउटपुट
Pattern found at position: 2