接尾辞配列（サフィックス配列）とは？仕組みとC++での実装・パターン検索手法

与えられた文字列からは、すべての可能な接尾辞（サフィックス）を取り出すことができます。これらの接尾辞を辞書式順序でソートすることで得られるのが「接尾辞配列」です。また、接尾辞配列は接尾辞木（サフィックスツリー）を用いて構成することも可能で、接尾辞木に対してDFS（深さ優先探索）で走査を行うことでも得られます。

接尾辞配列を利用すれば、接尾辞の検索を線形時間で行えるだけでなく、二分探索に近い手法によって文字列中の部分文字列（パターン）も高速に発見できます。

計算量

このパターン検索アルゴリズムの時間計算量は O(m log n) です（m はパターンの長さ、n はテキストの長さ）。

入力と出力

入力:
メイン文字列: "BANANA"、パターン: "NAN"
出力:
パターンが見つかった位置: 2

アルゴリズム

fillSuffixArray（text, suffArray）

入力: メイン文字列

出力: 接尾辞の配列

開始
    n := テキストの長さ
    サイズ n の allSuffix として接尾辞配列を定義

    i := 0 から n-1 まで繰り返し:
        allSuffix[i].index := i
        allSuffix[i].suff := text の i 文字目以降の部分文字列
    繰り返し終了

    allSuffix 配列をソートする
    ソート済み接尾辞のインデックスを suffArray に格納する
終了

suffixArraySearch（text, pattern, suffArray）

入力: メイン文字列、パターン、接尾辞配列

出力: パターンが見つかった位置

開始
    patLen := パターンの長さ
    strLen := テキストの長さ
    left := 0
    right := strLen - 1

    left <= right の間繰り返し:
        mid := left + (right - left) / 2
        tempStr := text の suffArray[mid] 文字目以降の部分文字列
        result := tempStr と pattern をパターンの長さ分だけ比較した結果

        もし result = 0 ならば:
            見つかった位置を出力する
        もし result < 0 ならば:
            right := mid - 1
        それ以外:
            left := mid + 1
    繰り返し終了
終了

BANANAの場合の動作例

文字列「BANANA」の各接尾辞を辞書式順序に並べ替えると、接尾辞配列は [5, 3, 1, 0, 4, 2] となります（A → ANA → ANANA → BANANA → NA → NANA の順）。この配列に対して「NAN」を二分探索すると、「NANA」（開始位置2）が一致するため、位置2に出力されます。

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) {     //ソート用に2つの文字列を比較
    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);     //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;
    }
}

実行結果

Pattern found at position: 2