Построение префикса Trie в C++, Suffix Trie

Question

Я использовал video, чтобы понять префикс trie (хотя в конце концов я пытаюсь добраться до суффикса trie в конце), однако ссылка на образец кода сломана, поэтому я подошел с этим из видео, есть две функции, т.е. вставки и поиска, как показано ниже

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; 
} 

Затем реализуется основной следующим образом:

int main(){ 
node* head=NULL; 

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

} 

и я получаю следующий вывод: не найдены

Это сбивает с толку, так как ab находится в строке s.

И, наконец, я пытаюсь понять эту строку:

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

означает ли это, мы получаем код ASCII для «а», а затем вычесть из ASCII код текущего символа?

Спасибо

Answer 1

Есть некоторая разница между суффиксов и префиксов деревьев.

Приставка дерево - это дерево, которое содержит все слова (или некоторые другие куски, разделенных некоторый символ) из данного текста. Например. для текста «у вас есть текст», дерево префикса содержит 4 слова: [«вы», «есть», «а», «текст»] (но не «hav»).

Суффикс дерево - это дерево префикс, который содержит все суффиксыот данного слова. Например. для строки «abacaba» дерево суффиксов содержит 7 слов: [«abacaba», «bacaba», «acaba», «caba», «aba», «ab», «a»].

Наилучшая реализация дерева суффиксов основана на реализации дерева префикса, который заполняется всеми подстроками некоторой входной строки в O (N^2) (поэтому в коде вы должны вставить все суффиксы строки S в Trie), но вы можете найти более умный Ukkonen's algorithm, который работает в линейном режиме.

Обычно дерево префикса используется, когда вы хотите найти слово (например, из какого-либо словаря и т. Д.) В тексте; дерево суффикса, используемое для нахождения некоторого шаблона в качестве подстроки текста.

Итак, вы должны выбрать, какое дерево вам нужно, зависит от вашей проблемы.

И да, вы правы в своем последнем вопросе.