## Algorithm/Insights

This algorithm uses trie data structure for efficient longest prefix matching. You might want to visit previous posts for more details about trie data structure,constructing a trie, insertion and search algorithms, its comparison with other data structures.

An example trie data structure for following (key, value) pairs

("cat",9),("cam",1),("word",5),("name",8)("na",2), ("nam",5).

First step of this algorithm is to construct a trie by inserting words of the given dictionary in it. Once this trie is constructed, we just need to traverse along the trie by taking out characters of the input string one by one. During this traversal, we keep track of the characters of the string that have been matched and update the longest prefix matched when a leaf node of trie is visited. Algorithm terminates if it comes across a null TrieNode during traversal or if the complete input string is matched. Null TrieNode visit indicates that there are no more nodes to visit in this path.

Let's run through an example for more clear understanding. Say we are given input string as "camera" and a dictionary with words - cat, cam, word, name, na, nam. We have chosen to use words which are keys in above shown trie. The step by step execution of the algorithm goes as follows for input string "camera"

1. Initialize charSequenceMatched and longestPrefixMatched to empty strings. Go to root node of the trie.

2. Make currentNode = root.children[getIndex('c')]. getIndex('c') would return 2 in the alphabet system of 'a'-'z'.

3. currentNode is now pointing to node 'c' at level-1. Update charSequenceMatched to string "c". Read the next character of the input string that is 'a' and update currentNode = currentNode.children[getIndex('a')].

4. currentNode is now pointing to node 'a' at level-2. Update charSequenceMatched to string "ca". Read the next character of the input string which is 'm' and update currentNode = currentNode.children[getIndex('m')].

5. currentNode is now pointing to node 'm' at level-3. Update charSequenceMatched to string "cam". This node is leafNode, longestPrefixMatched is updated to charSequenceMatched that is "cam". Read the next character of the input string which is 'e' and update currentNode = currentNode.children[getIndex('e')].

6. At this point, currentNode is null and hence the algorithm terminates and returns longestPrefixMatched which is "cam".

Please checkout code snippet and algorithm visualization section for more details of the algorithm.