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.

Answer 2

You can use a kind of index over all nodes.

Dictionary<char,List<TrieNode>> nodeIndex;

Now if you want to search for example for "Fi" iterate over nodeIndex and search as before. In case you found something on that iteration you have to prepend the found substrings with the string leading to the actual node.

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

Maybe there are some yet missing properties you have to implement.