Returning multiple nodes when searching for a tree / trie?

I built a suffix trie, a tree containing all the suffixes of a string, where each node contains only one character with a suffixNode at the end of each path, which contains the locations of the suffixes within the string.

Let's say my triple contains the words "Cat", "Car" and "Can", and I want to search for "Ca", the result should return 3 suffixes since the search string is in three different places. I managed to find a tree for "Ca", but once I get to that point, I don't know how to continue traversing the children of the "a" node to find all the suffix nodes.

I was thinking to use some kind of collection to add suffix nodes and then return the collection. Does this approach make sense, or are there better solutions?

I solved the search problem below. The reason it didn't return any nodes has to do with tree creation and differences between nodes:

public void SearchTrie(Node parent, String s, List<SuffixNode> suffixes)
    {
        Node n = FindNode(parent, s);
        FindSuffixes(n, suffixes);
    }

    private void FindSuffixes(Node parent,List<SuffixNode> suffixes)
    {            
        if (parent is SuffixNode)
        {
            suffixes.Add((SuffixNode)parent);
        }
        else
        {
            foreach (KeyValuePair<char, Node> child in parent.children)
            {
                FindSuffixes(child.Value, suffixes);
            }
        }
    }

    private Node FindNode(Node parent, String s)
    {
        if ((s.Length == 1) && parent.children.ContainsKey(s[0]))
        {
            Node n = parent.children[s[0]];
            return n;
        }

        while (s[0].ToString() != "")
        {
            if (parent.children.ContainsKey(s[0]))
            {
                if ((s.Length > 1))
                {
                    return FindNode(parent.children[s[0]], s.Substring(1));
                }

            }
            else
            {
                break;
            }

        }

        return null;
    }

      

Node:

class Node
{
    public char label;
    public Node parent;
    public Dictionary<char,Node> children;

    public Node(Node NewParent, char NewLabel)
    {
        this.parent = NewParent;
        this.label = NewLabel;
        children=new Dictionary<char,Node>();
    }
}

      

+3


source to share


1 answer


I was thinking to use some kind of collection to add suffix nodes and then return the collection.

This will be the first choice.

... or are there better solutions?



There are other solutions like

  • filling the list provided by the caller
  • use an iterator block with yield return

But without any special requirement, fill in a List<string>

and return it as IEnumerable<string>

.

+3


source







All Articles