Thuật toán Kasai xây dựng mảng LCP từ Suffix Array

Giới thiệu

Kasai's Algorithm xây dựng mảng Longest Common Prefix (LCP) từ suffix array. Trước tiên xây suffix array, sau đó Kasai tính LCP.

Độ phức tạp xây suffix array: O(m log n), Kasai: O(n).

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

Đầu vào: Văn bản: "banana"
Đầu ra: Suffix Array : 5 3 1 0 4 2
Common Prefix Array : 1 3 0 0 2 0

Thuật toán

buildSuffixArray(text)

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

Đầu ra: Suffix array

Begin
  n := kích thước text
  với i := 0 đến n làm:
    suffArray[i].index := i
    suffArray[i].rank[0] := text[i]
    nếu (i+1) < n thì suffArray[i].rank[1] := text[i+1]
    ngược lại suffArray[i].rank[1] := -1
  done
  lặp:
    sắp xếp suffix array
    định nghĩa mảng index lưu chỉ số
    với k := 4 đến (2*n)-1, tăng k = k*2 làm:
      currRank := 0, prevRank := suffArray[0].rank[0]
      suffArray[0].rank[0] := currRank
      index[suffArray[0].index] = 0
      với chỉ số i của mọi ký tự text làm:
        nếu suffArray[i].rank[0] = prevRank VÀ suffArray[i].rank[1] = suffArray[i-1].rank[1] thì
          prevRank := suffArray[i].rank[0]
          suffArray[i].rank[0] := currRank
        ngược lại
          prevRank := suffArray[i].rank[0]
          suffArray[i].rank[0] := currRank + 1
          currRank := currRank + 1
          index[suffArray[i].index] := i
      done
      với chỉ số i của mọi ký tự text làm:
        nextIndex := suffArray[i].index + k/2
        nếu nextIndex < n thì suffArray[i].rank[1] := suffArray[index[nextIndex]].rank[0]
        ngược lại suffArray[i].rank[1] := -1
      done
      sắp xếp suffArray
    done
    với chỉ số i của text làm: chèn suffArray[i].index vào suffVector
  End

kasaiAlgorithm(text, suffVector)

Đầu vào: Văn bản chính và vector hậu tố

Đầu ra: Mảng LCP

Begin
  n := kích thước suffVector
  định nghĩa longPrefix kích thước n điền 0
  định nghĩa suffInverse kích thước n điền 0
  với chỉ số i của suffVector làm:
    suffInverse[suffVector[i]] = i
  done
  k := 0
  với i := 0 đến n-1 làm:
    nếu suffInverse[i] = n-1 thì k := 0, continue
    j := suffVector[suffInverse[i]+1]
    trong khi (i+k) 0 thì giảm k 1
  done
  trả về longPrefix
End

Ví dụ (C++)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct suffix { int index; int rank[2]; };

bool compare(suffix s1, suffix s2) {
  if(s1.rank[0] == s2.rank[0]) {
    if(s1.rank[1] < s2.rank[1]) return true;
    else return false;
  } else {
    if(s1.rank[0] < s2.rank[0]) return true;
    else return false;
  }
}

vector<int> buildSuffixArray(string mainString) {
  int n = mainString.size();
  suffix suffixArray[n];
  for (int i = 0; i < n; i++) {
    suffixArray[i].index = i;
    suffixArray[i].rank[0] = mainString[i] - 'a';
    suffixArray[i].rank[1] = ((i+1)0) k--;
  }
  return longPrefix;
}

void showArray(vector<int> vec) {
  for (auto it = vec.begin(); it < vec.end(); it++) cout << *it << " ";
  cout << endl;
}

int main() {
  string mainString = "banana";
  vector<int> suffixArray = buildSuffixArray(mainString);
  cout << "Suffix Array : " << endl; showArray(suffixArray);
  vector<int> commonPrefix = kasaiAlgorithm(mainString, suffixArray);
  cout << "\nCommon Prefix Array : " << endl; showArray(commonPrefix);
}

Kết quả đầu ra

Suffix Array : 5 3 1 0 4 2
Common Prefix Array : 1 3 0 0 2 0