Mảng Hậu tố (Suffix Array)

Giới thiệu

Từ một chuỗi cho trước, ta lấy tất cả hậu tố có thể. Sau khi sắp xếp các hậu tố theo thứ tự từ điển (lexicographical), ta được mảng hậu tố (suffix array). Mảng hậu tố cũng có thể xây từ cây hậu tố qua duyệt DFS.

Suffix array giúp tìm hậu tố trong thời gian tuyến tính, và tìm chuỗi con bằng thủ tục kiểu tìm kiếm nhị phân.

Độ phức tạp: O(m log n)

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

Đầu vào: Văn bản: "BANANA", Mẫu: "NAN"
Đầu ra: Pattern found at position: 2

Thuật toán

fillSuffixArray (text, suffArray)

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

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

Begin
  n := độ dài text
  định nghĩa mảng hậu tố allSuffix kích thước n
  với i := 0 đến n-1 làm:
    allSuffix[i].index := i
    allSuffix[i].suff := chuỗi con của text từ (i đến cuối)
  done
  sắp xếp mảng allSuffix
  lưu chỉ số của mảng hậu tố đã sắp xếp vào suffArray.
End

suffixArraySearch (text, pattern, suffArray)

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

Đầu ra: Vị trí tìm thấy mẫu

Begin
  patLen := kích thước pattern
  strLen := kích thước text
  left := 0, right := strLen - 1
  trong khi left <= right làm:
    mid := left + (right - left)/2
    tempStr := chuỗi con của text từ suffArray[mid] đến cuối
    result := so sánh tempStr và pattern đến độ dài pattern
    nếu result = 0 thì in vị trí
    nếu result < 0 thì right := mid - 1
    ngược lại left := mid + 1
  done
End

Ví dụ (C++)

#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) {
  if(suff1.suff < suff2.suff) return true;
  return false;
}

void fillSuffixArray(string mainString, int suffArr[]) {
  int n = mainString.size();
  suffix allSuffix[n];
  for(int i = 0; i < n; i++) {
    allSuffix[i].index = i;
    allSuffix[i].suff = mainString.substr(i);
  }
  sort(allSuffix, allSuffix + n, comp);
  for(int i = 0; i < n; i++) suffArr[i] = allSuffix[i].index;
}

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

Kết quả đầu ra

Pattern found at position: 2