18.8 Given a string s and an array of smaller strings T, design a method to search s for each small string in T.
这道题给我们一个字符串s，和一个字符串数组T，让我们找T中的每一个小字符串在s中出现的位置，这道题很适合用后缀树Suffix Tree来做，LeetCode中有几道关于前缀树(Prefix Tree, Trie)的题，Implement Trie (Prefix Tree)，Word Search II，和 Add and Search Word - Data structure design 。前缀树和后缀树比较相似，都是很重要的数据结构，在解决特定问题时非常有效，具体讲解请参见这个帖子。参见代码如下：
class SuffixTreeNode { public: unordered_map<char, SuffixTreeNode*> children; char value; vector<int> indexes; void insertString(string s, int idx) { indexes.push_back(idx); if (!s.empty()) { value = s[0]; SuffixTreeNode *child; if (children.count(value)) { child = children[value]; } else { child = new SuffixTreeNode(); children[value] = child; } string remainder = s.substr(1); child->insertString(remainder, idx); } } vector<int> search(string s) { if (s.empty()) return indexes; char first = s[0]; if (children.count(first)) { string remainder = s.substr(1); return children[first]->search(remainder); } return {}; } }; class SuffixTree { public: SuffixTreeNode *root = new SuffixTreeNode(); SuffixTree(string s) { for (int i = 0; i < s.size(); ++i) { string suffix = s.substr(i); root->insertString(suffix, i); } } vector<int> search(string s) { return root->search(s); } };
本文转自博客园Grandyang的博客，原文链接： 搜索字符串[CareerCup] 18.8 Search String，如需转载请自行联系原博主。
