面试题 17.17. 多次搜索#

1
给定一个较长字符串big和一个包含较短字符串的数组smalls，
2

3
设计一个方法，根据smalls中的每一个较短字符串，对big进行搜索。
4

5
输出smalls中的字符串在big里出现的所有位置positions，
6

7
其中positions[i]为smalls[i]出现的所有位置。
8

9
示例：
10

11
输入：
12
big = "mississippi"
13
smalls = ["is","ppi","hi","sis","i","ssippi"]
14
输出： [[1,4],[8],[],[3],[1,4,7,10],[5]]
15
提示：
16

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

1
struct Trie
2
{
3
    int index = -1;
4
    Trie* next[26];
5
};
6
class Solution {
7
public:
8
    vector<vector<int>> multiSearch(string big, vector<string>& smalls) {
9
        Trie* root = new Trie();
10
        int n = smalls.size(), m = big.size();
11
        for (int i = 0; i < n; i++)
12
        {
13
            Trie* p = root;
14
            for (auto s : smalls[i]) {
15
                if (p -> next[s - 'a'] == nullptr)
16
                {
17
                    Trie* q = new Trie();
18
                    p -> next[s - 'a'] = q;
19
                }
20
                p = p -> next[s - 'a'];
21
            }
22
            p -> index = i;
23
        }
24

25
        vector<vector<int>> ans(n);
26

27
        for (int i = 0; i < m; i ++)
28
        {
29
            Trie* p = root;
30
            int j = i;
31
            while (j < m && p -> next[big[j] - 'a'] != nullptr)
32
            {
33
                p = p -> next[big[j] - 'a'];
34
                if (p -> index != -1)
35
                    ans[p -> index].push_back(i);
36
                j++;
37
            }
38
        }
39
        return ans;
40
    }
41
};