C++で接頭辞トライを作成する接尾辞Trie

Question

私はvideoを使用して接頭辞トライを理解していますが（最終的に接尾辞トライに到達しようとしていますが）、サンプルコードへのリンクが壊れています

int main(){ 
node* head=NULL; 

string s="abbaa"; 
init(); 
insert(s); 
if(search("ab")==true) cout<<"Found"<<endl; 
else cout<<"Not found"<<endl; 

} 

そして、私は次の出力を取得しています：

が見つかりませんが、ビデオからこれで、次のように二つの機能、すなわち次に

void insert(string word) 
{ 
    node* current=head; 
    current->prefix_count++; 
    for(unsigned int i=0;i<word.length();++i) 
    { 
     int letter=(int)word[i]-(int)'a'; 
     if (current->child[letter]==NULL) 
      current->child[letter]=new node(); 
     current->child[letter]->prefix_count++; 
     current=current->child[letter]; 
      } 
    current->is_end=true; 
} 

bool search(string word) 
{ 
    node *current=head; 
    for(int i=0;i<word.length();++i) 
    { 
     if(current->child[((int)word[i]-(int)'a')]==NULL) 
      return false; 
     current=current->child[((int)word[i]-(int)'a')]; 
    } 
    return current->is_end; 
} 

以下のように挿入して、検索メインを実装があります

文字列sにabがあるので、これは混乱します。

そして最後に、私はこの行を理解しようとしています：

int letter=(int)word[i]-(int)'a'; 

これは我々が「A」のASCIIコードを取得して、現在の文字のASCIIコードから減算されている意味ですか？

ありがとうございます

Answer 1

接尾辞と接頭辞のツリーにはいくつかの違いがあります。

プレフィックスツリー - それは、与えられたテキストからすべての単語（またはいくつかの記号で区切られたいくつかの他のチャンク）を含むツリー、です。例えば。プレースメントツリーには、["あなた"、 "持っている"、 "a"、 "テキスト"]（但し、 "hav"ではなく）の4つの単語が含まれています。

接尾辞木 - それは、与えられた単語からすべてのサフィックスを含まプレフィックスツリー、です。例えば。 "abacaba"、 "bacaba"、 "acaba"、 "caba"、 "aba"、 "ab"、 "a"の7つの単語が含まれています。

サフィックスツリーのナイーブな実装は、入力文字列のすべての部分文字列をO（N^2）で埋め込んだプレフィックスツリーの実装に基づいています（コードでは、文字列Sのすべての接尾辞をTrieに挿入する必要があります）。線形時間で働くより巧妙なUkkonen's algorithmを見つけることができます。

一般的に、テキスト内の単語（たとえば、辞書などから）を検索するときに使用するプレフィックスツリー。テキストの部分文字列としていくつかのパターンを見つけるのに使用される接尾辞ツリー。

したがって、問題に応じて必要なツリーを選択する必要があります。

はい、あなたは最後の質問に間違いありません。