后缀数组

从给定的字符串中，我们可以获得所有可能的后缀。在按字典顺序对后缀进行排序之后，我们可以获得后缀数组。后缀数组也可以使用后缀树来形成。通过使用后缀树的DFS遍历，我们可以获得后缀数组。后缀数组有助于找到线性时间的后缀。我们还可以通过使用二进制搜索类型过程使用后缀数组查找子字符串。

时间复杂度为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