Mảng hậu tố

Từ một chuỗi đã cho, chúng ta có thể nhận được tất cả các hậu tố có thể có. Sau khi sắp xếp các hậu tố theo thứ tự từ vựng, chúng ta có thể nhận được mảng hậu tố. Mảng hậu tố cũng có thể được hình thành bằng cách sử dụng cây hậu tố. Bằng cách sử dụng tính năng duyệt DFS của các cây hậu tố, chúng ta có thể nhận được các mảng hậu tố. Mảng hậu tố rất hữu ích để tìm hậu tố theo thời gian tuyến tính. Chúng tôi cũng có thể tìm thấy các chuỗi con bằng cách sử dụng mảng hậu tố bằng cách sử dụng quy trình loại tìm kiếm nhị phân.

Độ phức tạp về thời gian là O (m log n)

Đầu vào và Đầu ra

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

Thuật toán

fillSuffixArray (văn bản, hậu tố)

Đầu vào: Chuỗi chính

Đầu ra: Mảng các hậu tố

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

Hậu tốArraySearch (văn bản, mẫu, hậu tố)

Đầu vào: Chuỗi chính, mẫu và mảng hậu tố

Đầu ra - vị trí nơi các mẫu được tìm thấy

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

Ví dụ

#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;
   }
}

Đầu ra

Pattern found at position: 2