给定一个较长字符串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]]
最简单的就是拿smalls中的每一个字符串到big中寻找出现的位置。
class Solution{ public: vector<vector<int>> multiSearch(string big,vector<string>& smalls) { vector<vector<int>> vv;//vv就是返回的二维向量 for(int i=0;i<smalls.size();i++) { //拿smalls中的每一个字符串和big做匹配查找 vector<int> v;//v是一个向量，用来存储当前的查找结果 string temp_big=big; //每次用一个temp_big来作为big，因为在每次查找的过程中，对于字符串的find是从头开始查找， //所以当找到第一次后，需要把找到的那个位置的字符替换为一个' '，即空字符 for(int j=0;j<temp_big.length();j++) { if(smalls[i]=="") break;//因为C++中任意的字符串都能匹配""，调用find函数后都返回0 int location=temp_big.find(smalls[i]); if(location>=0){ v.push_back(location); temp_big[location]=' '; //因为下一次调用find函数还是从头开始查找，所以需要把上一次找到的位置的字符置换为空字符，这样下一次find时候就不会再重新计算这个位置。 } else //说明没有找到 break; } vv.push_back(v); } return vv; } };除了这个方法还有用trie树，也就是字典树的。 但是我利用字典树的方法超时了，不过可以证明代码还是可以运行的，下面我把用trie树的代码也写上。
在写之前我们可以直接看leetcode上关于trie树的题。
可以把Trie树理解为每一个节点有26个子节点而不是二叉树只有两个。 通过一个大词典中的所有单词构造一个Trie树，然后就可以快速知道是否我们要查找的单词在这个Trie树中。
class Trie{ private: Trie* child[26]; bool is_word; public: Trie(){ for(int i=0;i<26;i++) child[i]=NULL; is_word=false; } void insert(string word) { Trie *p=this; for(int i=0;i<word.length();i++) { if(!p->child[word[i]-'a']) p->child[word[i]-'a']=new Trie(); p=p->child[word[i]-'a']; } p->is_word=true; } bool search(string word) { Trie *p=this; for(int i=0;i<word.length();i++) { if(p->child[word[i]-'a']) p=p->child[word[i]-'a']; else return false; } return p->is_word;//比如Trie树中有likes，如果word是like，那么返回结果就是false } bool startsWith(string word) { Trie *p=this; for(int i=0;i<word.length();i++) { if(p->child[word[i]-'a']) p=p->child[word[i]-'a']; else return false; } return true;//比如Trie树中有likes，如果word是like，那么返回结果就是true } };回到多次搜索这个题，如何利用trie树呢。 看评论说是利用smalls中的所有词作为词典构造trie树，然后对于big，从头到尾遍历一遍即可。
注意此时的trie树每一个叶子节点还应该多加一个位置用来存储当前这个单词是smalls的第几个单词
class Trie{ private: Trie *next[26]; bool is_word; int word_id; public: Trie(){ for(int i=0;i<26;i++) next[i]=NULL; is_word=false; } void insert(string word,int word_index) { Trie *p=this; for(int i=0;i<word.length();i++) { if(p->next[word[i]-'a']==NULL) p->next[word[i]-'a']=new Trie(); p=p->next[word[i]-'a']; } p->is_word=true; p->word_id=word_index; } int search(string word) { Trie *p=this; for(int i=0;i<word.length();i++) { if(p->next[word[i]-'a']) p=p->next[word[i]-'a']; else return -1; } if(p->is_word) return p->word_id; else return -1; } }; class Solution{ public: vector<vector<int>> multiSearch(string big, vector<string>& smalls) { Trie *p=new Trie(); vector<vector<int>> vv; set<int> length_set; //length_set的作用是记录smalls中每一个字符串的长度，以集合的形式存储，不需要重复。 //这是因为当利用smalls构建好trie后，我们会对于每一个字符串长度，然后从头到尾的遍历big。 //具体的，smalls的第一个单词长度是2，那么我们会对mississippi每两个字符去trie树中寻找是否在trie中有这个两个字母组成的单词，因此 //你会发现，当结束查找后，我们其实已经找遍了big中所有长度为2的单词，所以此时不仅得到is的位置[1,4]，也得到了hi的位置为[]。 for(int i=0;i<smalls.size();i++) { vector<int> v; p->insert(smalls[i],i); vv.push_back(v); length_set.insert(smalls[i].length()); } set<int>::iterator it=length_set.begin(); for(int i=0;it!=length_set.end();i++,it++) { for(int j=0;j<big.length();j++) { if((j+(*it))>big.length()) break; int k=p->search(big.substr(j,*it)); if(k>=0&&(smalls[i]!="")) { vv[k].push_back(j); } } } return vv; } }; //这是一个超时的代码。