Given a dictionary of words and an input string, find the longest prefix of the string which is also a word in dictionary.

Problem : Given a dictionary of words and an input string, find the longest prefix of the string which is also a word in dictionary.

Examples:

Let the dictionary contains the following words:
{are, area, base, cat, cater, children, basement}

Below are some input/output examples:
--------------------------------------
Input String            Output
--------------------------------------
caterer                 cater
basemexy                base
child                   < Empty >
Solution
We build a Trie of all dictionary words. Once the Trie is built, traverse through it using characters of input string. If prefix matches a dictionary word, store current length and look for a longer match. Finally, return the longest match.
Following is Java implementation of the above solution.

public String getLongestMatchingPrex(String input){
String result="";
int inputLen = input.length();
int index=0, prevMatch=0;
TrieNode current = root, childNode = null;
char ch;
while (index < inputLen) {
ch = input.charAt(index);
childNode = current.subNode(ch);
if (childNode != null) {
result += ch;
current = childNode;
// If this is end of a word, then update prevMatch
if (current.isEndOfString){
prevMatch = index + 1;
}
}else{
break;
}
index++;
}

if (!current.isEndOfString){
return result.substring(0, prevMatch);
}

return result;
}