static CharTrie ahoCorasickBuild(String[] pats) {
        CharTrie root = new CharTrie();
        for (int i = 0; i < pats.length; i++) {
            CharTrie cur = root;
            for (int j = 0; j < pats[i].length(); j++) {
                char c = pats[i].charAt(j);
                if (cur.children[c] == null) cur.children[c] = new CharTrie();
                cur = cur.children[c];
            }
            cur.matches.add(i);
        }

        Queue<CharTrie> queue = new LinkedList<CharTrie>();  // Java5
        for (int i = 0; i < root.children.length; i++) {
            if (root.children[i] == null) root.children[i] = root;
            else {
                root.children[i].fail = root;
                queue.add(root.children[i]);
            }
        }
        while (!queue.isEmpty()) {
            CharTrie par = queue.poll();
            for (int i = 0; i < par.children.length; i++) {
                CharTrie child = par.children[i];
                if (child == null) continue;
                queue.add(child);

                CharTrie fail = par.fail;
                while (fail.children[i] == null)
                    // 子の失敗遷移は、親の失敗遷移先からその文字で進めるところ
                    fail = fail.fail;
                child.fail = fail.children[i];
                child.matches.addAll(child.fail.matches);
            }
        }
        return root;
    }