Effective search with contains

Question

I have a Trie data structure, it searches 100 000 elements in a blink of an eye. However it only searches words which start with the searched string, for example "Fi" will find "Final" but won't find "GooFi" and I want it to return "GooFi" too. That is why I am here asking you guys if this is the correct structure in this case. I implemented it myself, wrote unit tests so it's working so far. What I need is a hint how my goal can be achieved, I don't want anyone to write the code for me, that is not why I am here. Anyways here's my search implementation:

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

Any help is greatly appreciated.

Answer 1

https://github.com/gngeorgiev/Trie

Here is the repo of the Trie if anyone ever needs it. Supports prefix and substring search.