gistfile1.java

import com.google.common.base.Predicate;
import com.google.common.collect.Iterables;
import com.google.common.collect.Lists;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

import static java.lang.String.format;
import static java.lang.System.out;

public class AlienTree {
    static class Node {
        final Character letter;
        final List<Node> children = Lists.newArrayList();

        Node(Character letter) {
            this.letter = letter;
        }
    }

    static class WordTree {
        final Node root = new Node(null);

        void addWord(String word) {
            addWordHelper(root, word);
        }

        void addWordHelper(Node node, String fragment) {
            char childChar = fragment.charAt(0);

            Node child = Iterables.find(node.children, new HasChar(childChar), null);

            if (child == null) {
                child = new Node(childChar);
                node.children.add(child);
            }

            if (fragment.length() > 1)
                addWordHelper(child, fragment.substring(1));
        }
    }

    static class CaseCounter {
        static void count(BufferedReader reader) throws IOException {
            String[] header = reader.readLine().split(" ");

            int l = Integer.parseInt(header[0]);
            int d = Integer.parseInt(header[1]);
            int n = Integer.parseInt(header[2]);

            WordTree tree = new WordTree();
            for (int i = 0; i < d; i++)
                tree.addWord(reader.readLine());

            for (int i = 0; i < n; i++)
                out.println(format("Case #%d: %d", i + 1, getInstanceCount(reader.readLine(), tree)));
        }

        static int getInstanceCount(String pattern, WordTree tree) {
            List<List<Character>> groups = Lists.newArrayList();

            char[] chars = pattern.toCharArray();

            for (int i = 0; i < chars.length; i++) {
                List<Character> group = Lists.newArrayList();
                if (chars[i] == '(') {
                    i++;
                    while (chars[i] != ')') {
                        group.add(chars[i]);
                        i++;
                    }
                } else {
                    group.add(chars[i]);
                }
                groups.add(group);
            }

            return getInstanceCountHelper(tree.root, groups);
        }

        static int getInstanceCountHelper(Node node, List<List<Character>> groups) {
            int levelCount = 0;

            // recursive case: there are more children and matching groups to go with them
            if (node.children.size() > 0 && groups.size() > 0)
                for (Character character : groups.get(0)) {
                    Node child = Iterables.find(node.children, new HasChar(character), null);

                    if (child != null) {
                        List<List<Character>> subGroup = groups.size() > 1
                            ? groups.subList(1, groups.size() - 1)
                            : new ArrayList<List<Character>>(0);

                        levelCount += getInstanceCountHelper(child, subGroup);
                    }
                }

            // base case: we arrived at a terminal node and are out of letters, indicating a matching word.
            else if (groups.size() == 0)
                levelCount = 1;

            return levelCount;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new FileReader(new File("input.txt")));
        CaseCounter.count(reader);
    }

    static class HasChar implements Predicate<Node> {
        private char nodeChar;

        private HasChar(char nodeChar) {
            this.nodeChar = nodeChar;
        }

        public boolean apply(Node node) {
            return node.letter.equals(nodeChar);
        }
    }
}