gold-17-17

给定一个较长字符串big和一个包含较短字符串的数组smalls，设计一个方法，根据smalls中的每一个较短字符串，对big进行搜索。输出smalls中的字符串在big里出现的所有位置positions，其中positions[i]为smalls[i]出现的所有位置。

示例：

输入：
big = "mississippi"
smalls = ["is","ppi","hi","sis","i","ssippi"]
输出： [[1,4],[8],[],[3],[1,4,7,10],[5]]

提示：

• 0 <= len(big) <= 1000
• 0 <= len(smalls[i]) <= 1000
• smalls的总字符数不会超过 100000。
• 你可以认为smalls中没有重复字符串。
• 所有出现的字符均为英文小写字母。

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[][] multiSearch(String big, String[] smalls) {
        if (big == null) {
            return new int[0][];
        }

        Trie rootTrie = new Trie();
        rootTrie.next = new Trie[26];

        addStr(rootTrie, big, 0);

        for (int i = 1; i < big.length(); i++) {
            addStr(rootTrie, big.substring(i), i);
        }

        int[][] result = new int[smalls.length][];
        for (int i = 0; i < smalls.length; i++) {
            result[i] = getIndexList(rootTrie, smalls[i]);
        }
        return result;
    }

    private class Trie {
        List<Integer> indexList;
        Trie[] next;
    }

    private void addStr(Trie trie, String str, int index) {
        char[] chars = str.toCharArray();
        Trie curTrie = trie;

        for (char ch : chars) {
            if (curTrie.next[ch - 'a'] == null) {
                curTrie.next[ch - 'a'] = new Trie();
                curTrie.next[ch - 'a'].indexList = new ArrayList<>();
                curTrie.next[ch - 'a'].next = new Trie[26];
            }
            curTrie.next[ch - 'a'].indexList.add(index);
            curTrie = curTrie.next[ch - 'a'];
        }
    }

    private int[] getIndexList(Trie rootTrie, String small) {
        if (small == null || small.length() == 0) {
            return new int[0];
        }

        char[] chars = small.toCharArray();
        Trie curTrie = rootTrie;
        for (char ch : chars) {
            if (curTrie.next[ch - 'a'] == null) {
                curTrie = null;
                break;
            }
            curTrie = curTrie.next[ch - 'a'];
        }


        if (curTrie == null) {
            return new int[0];
        }

        int[] result = new int[curTrie.indexList.size()];
        for (int i = 0; i < curTrie.indexList.size(); i++) {
            result[i] = curTrie.indexList.get(i);
        }
        return result;
    }
}
//leetcode submit region end(Prohibit modification and deletion)