接尾辞配列

指定された文字列から、可能なすべてのサフィックスを取得できます。辞書式順序で接尾辞を並べ替えると、接尾辞配列を取得できます。接尾辞配列は、接尾辞木を使用して形成することもできます。接尾辞木のDFSトラバーサルを使用することにより、接尾辞配列を取得できます。接尾辞配列は、線形時間で接尾辞を見つけるのに役立ちます。二分探索タイプの手順を使用して、接尾辞配列を使用して部分文字列を検索することもできます。

時間計算量はO（m log n）

入力と出力

Input:
Main String: “BANANA”, Pattern: “NAN”
Output:
Pattern found at position: 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（テキスト、パターン、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