อาร์เรย์ต่อท้าย

จากสตริงที่กำหนด เราจะได้ส่วนต่อท้ายที่เป็นไปได้ทั้งหมด หลังจากเรียงลำดับคำต่อท้ายในลำดับศัพท์แล้ว เราก็จะได้อาร์เรย์ส่วนต่อท้าย อาร์เรย์ต่อท้ายยังสามารถสร้างได้โดยใช้ทรีส่วนต่อท้าย โดยการใช้ DFS traversal ของ suffix tree เราจะได้ suffix arrays อาร์เรย์ต่อท้ายมีประโยชน์ในการค้นหาส่วนต่อท้ายในเวลาเชิงเส้น นอกจากนี้เรายังสามารถค้นหาสตริงย่อยโดยใช้อาร์เรย์ต่อท้ายโดยใช้ขั้นตอนประเภทการค้นหาแบบไบนารี

ความซับซ้อนของเวลาคือ O(m log n)

อินพุตและเอาต์พุต

Input:
Main String: “BANANA”, Pattern: “NAN”
Output:
Pattern found at position: 2

อัลกอริทึม

fillSuffixArray (ข้อความ, 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 (ข้อความ รูปแบบ 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<suff2.suff)
      return true;
   return false;
}

void fillSuffixArray(string mainString, int suffArr[]) {
   int n = mainString.size();
   suffix allSuffix[n];    //array to hold all suffixes

   for(int i = 0; i<n; i++) {
      allSuffix[i].index = i;
      allSuffix[i].suff = mainString.substr(i);    //from ith position to end
   }

   sort(allSuffix, allSuffix+n, comp);
   for(int i = 0; i<n; i++)
      suffArr[i] = allSuffix[i].index;    //indexes of all sorted suffix
}

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 and right for binary search

   while(left <= right) {
      int mid = left + (right - left)/2;
      string tempStr = mainString.substr(suffArr[mid]);
      int result = strCompare(pattern,tempStr, patLen);
   
      if(result == 0) {    //the pattern is found
        (*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