public class BoggleHybridTST
{
    private static final int R = 26;
    private static final int OFFSET = 'A';

    private static Node emptyNode = null;

    private Node[] roots = new Node[R * R];

    public class Node
    {
        private boolean isWord;
        private char c;
        private Node left, mid, right;

        public boolean isWord() { return isWord; }
        public String toString() { return "'"+c+"' "+isWord; }
    }

    public Node emptyNode() {
        if (emptyNode == null) {
            emptyNode = new Node();
        }
        return emptyNode;
    }

    public void put(String word)
    {
        int l = word.length();
        if (l < 3) return;
        int idx = ((word.charAt(0) - OFFSET) * R) + (word.charAt(1) - OFFSET);
        roots[idx] = put(roots[idx], word, 2);
    }

    private Node put(Node n, String word, int d)
    {
        char c = word.charAt(d);

        Node x = n;
        if (n == null) {
            x = new Node();
            x.c = c;
        }

        char ref = x.c;
        if (c < ref) {
            x.left = put(x.left, word, d);
        } else if (c == ref) {
            if (word.length() == (d + 1)) {
                x.isWord = true;
            } else {
                x.mid = put(x.mid, word, (d + 1));
            }
        } else {
            x.right = put(x.right, word, d);
        }

        return x;
    }

    public boolean contains(String word)
    {
        return (get(word) != null);
    }

    private Node get(String word)
    {
        if (word.length() < 3) return null;
        int idx = ((word.charAt(0) - OFFSET) * R) + (word.charAt(1) - OFFSET);
        return get(roots[idx], word, 2);
    }

    private Node get(Node n, String word, int d)
    {
        if (n == null) return null;

        char c = word.charAt(d);
        char ref = n.c;

        if (c < ref) {
            return get(n.left, word, d);
        } else if (c == ref) {
            if (word.length() == (d + 1)) {
                if (n.isWord) return n;
                else return null;
            }
            return get(n.mid, word, (d + 1));
        } else {
            return get(n.right, word, d);
        }
    }

    private Node get(Node n, char c)
    {
        if (n == null) return null;

        char ref = n.c;

        if (c < ref) {
            return get(n.left, c);
        } else if (c == ref) {
            return n;
        } else {
            return get(n.right, c);
        }
    }

    public Node filter(char c, Node n, StringBuilder s, int l)
    {
        if (n == null) return null;

        if (l > 2) {
            return get(n.mid, c);
        } else if (l == 2) {
            int idx = ((s.charAt(0) - OFFSET) * R) + (s.charAt(1) - OFFSET);
            Node root = roots[idx];
            if (root == null) return null;
            return get(root, c);
        } else {
            return n;
        }
    }

    public Node filter(char c, Node n, String s, int l)
    {
        if (n == null) return null;

        if (l > 2) {
            return get(n.mid, c);
        } else if (l == 2) {
            int idx = ((s.charAt(0) - OFFSET) * R) + (s.charAt(1) - OFFSET);
            Node root = roots[idx];
            if (root == null) return null;
            return get(root, c);
        } else {
            return n;
        }
    }

    public static void check(BoggleHybridTST tst, String word, boolean expected)
    {
        String status = "ok";
        if (tst.contains(word) != expected)
            status = "ERROR";
        System.out.println("check "+word+" : "+status);
    }

    // test client
    public static void main(String[] args)
    {

        BoggleHybridTST tst = new BoggleHybridTST();

        In in = new In(args[0]);
        String[] dictionary = in.readAllStrings();

        for (String word : dictionary)
            tst.put(word);

        check(tst, "ABC", true);
        check(tst, "BITE", false);
        check(tst, "BITEX", false);
        String word = "QUESTIONACCIA";
        check(tst, word, true);

        word += "X";
        StringBuilder s = new StringBuilder();
        Node n = tst.emptyNode();
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            n = tst.filter(c, n, s, i);
            s.append(c);
            System.out.println(s+" "+n);
        }
    }
}