Эффективный поиск с содержит

Question

У меня есть структура данных Trie, она мгновенно ищет 100 000 элементов в мгновение ока. Однако он ищет только слова, начинающиеся с искомой строки, например «Fi» найдет «Final», но не найдет «GooFi», и я хочу, чтобы он тоже возвращался «GooFi». Вот почему я здесь прошу вас, ребята, если это правильная структура в этом случае. Я сам его реализовал, написал модульные тесты, чтобы он работал до сих пор. Мне нужна подсказка, как моя цель может быть достигнута, я не хочу, чтобы кто-нибудь написал код для меня, и не потому, что я здесь. В любом случае, вот моя реализация:

public List<string> Seach(string word) 
{ 
    List<string> results = new List<string>(); 
    this.DoSearch(this.Root, 0, new StringBuilder(word), results); 
    return results; 
} 

private void DoSearch(TrieNode currentNode, int currentPositionInWord, StringBuilder word, List<string> results) 
{ 
    if (currentPositionInWord >= word.Length) 
    { 
     this.DfsForAllWords(currentNode, word, results); 
     return; 
    } 

    char currentChar = word[currentPositionInWord]; 

    bool containsKey = currentNode.Children.ContainsKey(currentChar); 
    if (containsKey) 
    { 
     if (currentPositionInWord == word.Length - 1) 
     { 
      results.Add(word.ToString()); 
     } 

     TrieNode child = currentNode.Children[currentChar]; 
     this.DoSearch(child, ++currentPositionInWord, word, results); 
    } 
} 

private void DfsForAllWords(TrieNode currentNode, StringBuilder word, List<string> results) 
{ 
    foreach (var node in currentNode.Children.ToArray()) 
    { 
     word.Append(node.Value.Value); 
     if (node.Value.IsWord) 
     { 
      results.Add(word.ToString()); 
     } 

     this.DfsForAllWords(node.Value, word, results); 
     word.Length--; 
    } 
} 

Любая помощь будет принята с благодарностью.

Answer 1

https://github.com/gngeorgiev/Trie

Вот репо из TRIE, если кто-либо нуждается в нем. Поддерживает поиск префикса и подстроки.

Answer 2

Вы можете использовать своего рода индекс по всем узлам.

Dictionary<char,List<TrieNode>> nodeIndex;

Теперь, если вы хотите найти, например, для «Фи» перебрать nodeIndex и поиск, как и раньше. Если вы нашли что-то на этой итерации, вы должны добавить найденные подстроки в строку, ведущую к фактическому узлу.

public List<string> Seach(string word) 
{ 
    List<string> results = new List<string>(); 

    foreach(var node in nodeIndex[word[0]]) 
    { 
     List<string> nodeResults = new List<string>(); 

     this.DoSearch(node, 0, new StringBuilder(word), nodeResults); 

     foreach(var nodeResult in nodeResults) 
     { 
      var text = string.Format("{0}{1}",node.Parent.Text, nodeResult); 
      results.Add(node.Parent.Text, nodeResult); 
     } 
    } 

    return results.Distinct().ToList(); 
} 

Возможно, есть некоторые недостающие свойства, которые вы должны реализовать.