[数据结构与算法]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）
链接：https://leetcode-cn.com/problems/multi-search-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

看见这种前缀，大概率字典树。有几点要注意：1)原本字典树的bool值我们用int，初始值赋为-1，然后在insert时，将这个值记为当前词在small里面的index；2)search的时候，把big按位截取，并记录开始截取的点index，当search到字典树中的“单词”时，依据insert时内置的int来记录进答案。

代码：

class?Solution?{

public:

????vector<vector<int>>?multiSearch(string&?big,?vector<string>&?small)?{

????????res?=?vector<vector<int>>(small.size());

????????for?(int?i?=?0;?i?<?small.size();?i++)?{

????????????if?(!small[i].empty())

????????????????insert(small[i],?i);

????????}

????????for?(int?i?=?0;?i?<?big.size();?i++)?{

????????????string?tmp?=?big.substr(i);

????????????search(tmp,?i);

????????}

????????return?res;

????}

private:

????vector<vector<int>>?res;

????class?Trie?{

????public:

????????Trie()?{};

????????Trie*?child[26]?=?{?nullptr?};

????????int?index?=?-1;

????};

????Trie*?trie?=?new?Trie();

????void?insert(string?&s,?int?index)?{

????????Trie*?tmp?=?trie;

????????for?(int?i?=?0;?i?<?s.size();?i++)?{

????????????int?c?=?s[i]?-?'a';

????????????if?(!tmp->child[c])?{

????????????????tmp->child[c]?=?new?Trie();

????????????}

????????????tmp?=?tmp->child[c];

????????}

????????tmp->index?=?index;

????}

????void?search(string&?s,?int?start)?{

????????Trie*?tmp?=?trie;

????????for?(int?i?=?0;?i?<?s.size();?i++)?{

????????????int?c?=?s[i]?-?'a';

????????????if?(tmp->child[c])?{

????????????????tmp?=?tmp->child[c];

????????????????if?(tmp->index?!=?-1)?{

????????????????????res[tmp->index].push_back(start);

????????????????}

????????????}

????????????else?{

????????????????return;

????????????}

????????}

????}

};