摘要：
=child[i]）｛deletechild[i]；child[i]=NULL；child[iindex]=newTrieNode；memset（root->；sz=str[left]；flag=true；right；left=0；=right；if（NULL==root||len<；=0）returnfalse；｝if（num==len）returntrue；
题目：
现有一个小写英文字母组成的字符串s和一个包含较短小写英文字符串的数组p，请设计一个高效算法，对于p中的每一个较短字符串，判断其是否为s的子串。
给定一个string数组p和它的大小n，同时给定string s，为母串，请返回一个bool数组，每个元素代表p中的对应字符串是否为s的子串。
保证p中的串长度小于等于8，且p中的串的个数小于等于500，同时保证s的长度小于等于1000。
此题参考他人代码，使用字典树即可以实现，实在是太赞了。
另外看到类似的做法，为AC自动机，其做法结合了字典树和KMP算法，没看懂，此处就不列出其相关代码。
待后续研究：http://www.cnblogs.com/huangxincheng/archive/2012/12/02/2798317.html
class Substr { private: struct TrieNode { char sz; bool flag; TrieNode* child[26]; TrieNode():sz(0),flag(false) { for (size_t i = 0; i < 26; i++) { child[i] = NULL; } } ~TrieNode() { for (size_t i = 0; i < 26; i++) { if (NULL != child[i]) { delete child[i]; child[i] = NULL; } } } }; void insert(const string& str,const int& left,const int& right, TrieNode* root) { int index = str[left] - 'a'; if (root->child[index] == NULL) { root->child[index] = new TrieNode; memset(root->child[index], 0, sizeof(TrieNode)); root->child[index]->sz = str[left]; } if (left==right) { root->child[index]->flag = true; return; } else { insert(str,left+1,right, root->child[index]); } } void build_TrieNode(const string& str, TrieNode* root) { int len = str.length(),left,right; if (len==0) return; left = 0;right = len - 1; for (; left <= right; left++) { insert(str, left, right, root); } } bool comparestr(TrieNode* root, const string& str) { int num = 0, len = str.length(), index; if (NULL == root || len <= 0) return false; TrieNode* p = root; while (p&&num < len) { index = str[num] - 'a'; if (p->child[index]) { ++num; } p = p->child[index]; } if (num == len) return true; else return false; } public: vector<bool> chkSubStr(vector<string> p, int n, string s) { vector<bool> res; int i, len = p.size(), strlen = s.length(); if (len <= 0 || strlen <= 0) return res; TrieNode *root = new TrieNode; memset(root, 0, sizeof(TrieNode)); build_TrieNode(s, root); for ( i = 0; i < len; i++) { if (comparestr(root, p[i])) res.push_back(true); else res.push_back(false); } delete root; return res; } }; int main(void) { { string str[]{"ello","world","test","hle","aaaa","ld"}; vector<string> strtemp(str, str + sizeof(str) / sizeof(string)); Substr test; auto var = test.chkSubStr(strtemp, strtemp.size(), "helloworld"); for each (auto vart in var) { cout << boolalpha << vart << endl; } } cin.get(); return 0; }