すべての接尾辞（サフィックス）からトライ木を構築してパターンを検索するアルゴリズム

テキストからすべての接尾辞（サフィックス）を生成し、それらを木構造（トライ木）としてまとめることができます。テキスト中に出現するあらゆるパターンは、必ずテキストのいずれかの接尾辞の接頭辞（プレフィックス）になっているという性質があります。この性質を利用し、すべての接尾辞からトライ木を事前に構築しておけば、任意の部分文字列を線形時間で検索できるようになります。

各接尾辞は文字列終端記号で終わるものとして扱います。検索時には、各ノードから次の文字に対応するパスが存在すれば前方へ進み、存在しなければ「パターンは見つからない」と判断して処理を終了します。

このアルゴリズムの時間計算量は O(m + k) です。ここで m は文字列の長さ、k はテキスト中にパターンが出現する回数を表します。

入力と出力

Input:
Main String: "ABAAABCDBBABCDDEBCABC". Pattern "ABC"
Output:
Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18

アルゴリズム

このアルゴリズムでは、「トライノード（trie node）」と呼ばれる特別なノードを使用します。トライノードは、自身を通過するすべての接尾辞のインデックス一覧と、子ノードへのリンク（アドレス）を保持します。

createTrie(root: trieNode, text)

入力： trieNode 型のルートノード

出力： 主文字列から構築された接尾辞ツリー

Begin
    for i := 0 to length of text, do
      substring from ith position to end as suffix, and add in index i in tire.
    done
End

findPat(pattern, node)

入力： 検索するパターンと、その接尾辞部分木をたどる起点となるノード

出力： パターンが見つかったインデックスのリスト

Begin
    if pattern size is 0, then
       return suffIndex of node
    if node.suff[patten[0]] ≠ φ, then
       return node.suff[pattern[0]].findPat(substring from 1 to end o pattern)
    else
       return φ
End

searchPat(pattern)

入力： 検索対象となるパターン

出力： パターンが見つかったテキスト内の位置（インデックス）のリスト

Begin
    define res as list.
    res := findPat(pattern)

    if res ≠ φ, then
       patLen := length of pattern
       for i := 0 to end of res list, do
          print all indexes where pattern was found
       done
End

C++ による実装例

#include<iostream>
#include<list>
#define MAXCHAR 256
using namespace std;

class trieNode {        //node to hold all suffixes
    private:
        trieNode *suff[MAXCHAR];
        list<int> *suffIndex;
    public:
        trieNode() {
            suffIndex = new list<int>;
            for (int i = 0; i < MAXCHAR; i++)
                suff[i] = NULL;         //no child initially
        }

        void addSuffix(string suffix, int sIndex);
        list<int>* searchPattern(string pat);
};

void trieNode::addSuffix(string suffix, int sIndex) {
    suffIndex->push_back(sIndex);           //store index initially

    if (suffix.size() > 0) {
        char cIndex = suffix[0];
        if (suff[cIndex] == NULL)           //if no sub tree present for this character
            suff[cIndex] = new trieNode();     //create new node
        suff[cIndex]->addSuffix(suffix.substr(1), sIndex+1);         //for next suffix
    }
}

list<int>* trieNode::searchPattern(string pattern) {
    if (pattern.size() == 0)
        return suffIndex;
    if (suff[pattern[0]] != NULL)
        return (suff[pattern[0]])->searchPattern(pattern.substr(1));     //follow to next node
    else
        return NULL;          //when no node are there to jump
}

class trieSuffix {        //trie for all suffixes
    trieNode root;
    public:
        trieSuffix(string mainString) {         //add suffixes and make trie
            for (int i = 0; i < mainString.length(); i++)
                root.addSuffix(mainString.substr(i), i);
        }

    void searchPat(string pattern, int *locArray, int *index);
};

void trieSuffix::searchPat(string pattern, int *locArray, int *index) {
    list<int> *res = root.searchPattern(pattern);
    // Check if the list of indexes is empty or not
    if (res != NULL) {
        list<int>::iterator it;
        int patLen = pattern.length();
        for (it = res->begin(); it != res->end(); it++) {
            (*index)++;
            locArray[(*index)] = *it - patLen;
        }
    }
}

int main() {
    string mainString = "ABAAABCDBBABCDDEBCABC";
    string pattern = "ABC";
    int locArray[mainString.size()];
    int index = -1;

    trieSuffix trie(mainString);
    trie.searchPat(pattern, locArray, &index);

    for(int i = 0; i <= index; i++) {
        cout << "Pattern found at position: " << locArray[i]<<endl;
    }

}

実行結果

Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18

このように、主文字列「ABAAABCDBBABCDDEBCABC」の中でパターン「ABC」は位置 4・10・18 の 3 箇所で見つかります。接尾辞トライ木を一度構築してしまえば、以降は同じテキストに対する何度でも高速なパターン検索が可能になるため、同一テキストへの繰り返し検索が必要な場面で特に有効な手法です。