Maior prefixo comum - Uma solução baseada em Trie em Java

Dado um dicionário de palavras e uma String de entrada, encontrar o prefixo mais longo da String que também é uma palavra no dicionário.

Exemplos:

Com um dicionário contendo as seguintes palavras:
{are, area, base, cat, cater, children, basement}

Alguns exemplos com entrada/saída:
-------------------------------------
String de entrada         Saída
-------------------------------------
caterer                   cater
basemexy                  base
child

Solução
Nós criamos uma Trie com todas as palavras do dicionário. Uma vez que a Trie foi construída, a percorremos usando os caracteres da String de entrada. Se o prefixo corresponde a uma palavra do dicionário, armazenamos o comprimento atual e procuramos por uma combinação mais longa. Finalmente, retornamos a maior combinação.

import java.util.HashMap;
// Trie Node, which stores a character and the children in a HashMap
class TrieNode {
    public TrieNode(char ch) {
        value = ch;
        children = new HashMap<>();
        bIsEnd = false;
    }
    public HashMap<Character,TrieNode> getChildren() { return children; }
    public char getValue()
    {
        return value;
    }
    public void setIsEnd(boolean val)
    {
        bIsEnd = val;
    }
    public boolean isEnd()
    {
        return bIsEnd;
    }
    private char value;
    private HashMap<Character,TrieNode> children;
    private boolean bIsEnd;
}


// Implements the actual Trie
class Trie {
    // Constructor
    public Trie()
    {
        root = new TrieNode((char)0);
    }

    // Method to insert a new word to Trie
    public void insert(String word) {
        // Find length of the given word
        int length = word.length();
        TrieNode crawl = root;
        // Traverse through all characters of given word
        for( int level = 0; level < length; level++)
        {
            HashMap<Character,TrieNode> child = crawl.getChildren();
            char ch = word.charAt(level);
            // If there is already a child for current character of given word
            if( child.containsKey(ch))
                crawl = child.get(ch);
            else
            {
                // Else create a child
                TrieNode temp = new TrieNode(ch);
                child.put( ch, temp );
                crawl = temp;
            }
        }
        // Set bIsEnd true for last character
        crawl.setIsEnd(true);
    }
    // The main method that finds out the longest string 'input'
    public String getMatchingPrefix(String input) {
        String result = ""; // Initialize resultant string
        int length = input.length(); // Find length of the input string
        // Initialize reference to traverse through Trie
        TrieNode crawl = root;
        // Iterate through all characters of input string 'str' and traverse
        // down the Trie
        int level, prevMatch = 0;
        for( level = 0 ; level < length; level++ )
        {
            // Find current character of str
            char ch = input.charAt(level);
            // HashMap of current Trie node to traverse down
            HashMap<Character,TrieNode> child = crawl.getChildren();
            // See if there is a Trie edge for the current character
            if( child.containsKey(ch) )
            {
                result += ch;
                //Update result
                crawl = child.get(ch); //Update crawl to move down in Trie
                // If this is end of a word, then update prevMatch
                if( crawl.isEnd() )
                    prevMatch = level + 1;
                }
                else
                    break;
        }
        // If the last processed character did not match end of a word,
        // return the previously matching prefix
        if( !crawl.isEnd() )
            return result.substring(0, prevMatch);
        else
            return result;
        }
    private TrieNode root;
}


// Testing class
public class Test {
    public static void main(String[] args) {
    Trie dict = new Trie();
    dict.insert("are");
    dict.insert("area");
    dict.insert("base");
    dict.insert("cat");
    dict.insert("cater");
    dict.insert("basement");
    String input = "caterer";
    System.out.print(input + ": ");
    System.out.println(dict.getMatchingPrefix(input));

    input = "basement";
    System.out.print(input + ": ");
    System.out.println(dict.getMatchingPrefix(input));
    input = "are";
    System.out.print(input + ": ");
    System.out.println(dict.getMatchingPrefix(input));
    input = "arex";
    System.out.print(input + ": ");
    System.out.println(dict.getMatchingPrefix(input));
    input = "basemexz";
    System.out.print(input + ": ");
    System.out.println(dict.getMatchingPrefix(input));
    input = "xyz";
    System.out.print(input + ": ");
    System.out.println(dict.getMatchingPrefix(input));
    }
}
Output:

caterer:
cater
basement:
basement
are:
are
arex:
are
basemexz:
base
xyz:

Complexidade de tempo: A complexidade de tempo para encontrar o maior prefixo é O(n), onde n é o tamanho da string de entrada.

Source
http://www.geeksforgeeks.org/longest-prefix-matching-a-trie-based-solution-in-java/