すべてのサフィックスのトライ

テキストから、すべてのサフィックスを生成してツリー構造を作成できます。テキストに表示されるすべてのパターンは、テキストで可能な接尾辞の1つの接頭辞でなければならないことを私たちは知っています。すべての接尾辞のTrieを作成することにより、線形時間で任意の部分文字列を見つけることができます。すべての接尾辞は、文字列終了記号で終わります。パスがある場合は各ノードから前方に移動し、そうでない場合はパターンが見つからないことを返します。

このアルゴリズムの場合、時間計算量は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

アルゴリズム

このアルゴリズムでは、トライノードと呼ばれる特別なノードを使用します。すべてのサフィックスのインデックスと別のトライノードアドレスをリンクとして保持します。

createTrie （ルート：trieNode、テキスト）

入力： タイプ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

例

#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