做红酒的网站有哪些企业seo自助建站系统
745. 前缀和后缀搜索 - 力扣（LeetCode）
可以参考这两个：
LeetCode第 208 题：实现Trie(前缀树)(C++)qq_32523711的博客-CSDN博客.
LeetCode第 211 题：添加与搜索单词 - 数据结构设计(C++)qq_32523711的博客-CSDN博客.
稍有区别。
这一题我们不需要查询单词存在与否，所以节点TrieNode就不需要isEnd成员变量了，因为我们只是需要处理前缀后缀而已。
前缀的处理很简单，顺着树查找，就是startsWith函数，后缀可以转化为前缀处理（相应地构建一棵后缀树，单词翻转即可）。
那么还有一点就是权值的处理，本题中权值就是该单词在数组words中的下标，处理方式就是给节点TrieNode增加一个成员变量weight，用于记录根节点到该节点的子串是哪些单词的前缀（也就是记录下标值），具体可以看图：
class Trie{
public:struct TrieNode{//每个节点都有一个权值数组，记录了路径会经过该节点的word的权值//根据题意，权值其实就是该单词在words中对应的下标//如果访问到这个节点，那么root到当前节点的子串是某些word的前缀//怎么找到这些word呢？这些word在原数组words中的下标存储在weight数组里面vector<int> weight;TrieNode* next[26] = {NULL};};Trie() : root(new TrieNode) {}void insert(string &word, int weight){TrieNode* p = root;for(int i = 0; i < word.size(); ++i){int idx = word[i] - 'a';if(p->next[idx] == NULL)p->next[idx] = new TrieNode;p = p->next[idx];p->weight.push_back(weight);//添加权值}}vector<int>* startsWith(string &prefix){TrieNode* p = root;for(int i = 0; i < prefix.size(); ++i){int idx = prefix[i] - 'a';if(p->next[idx] == NULL) return NULL;p = p->next[idx];}return &(p->weight);}
private:TrieNode* root;
};class WordFilter {
public:WordFilter(vector<string>& words) : pre(new Trie), suf(new Trie), count(words.size()){for(int i = 0; i < words.size(); ++i){pre->insert(words[i], i);reverse(words[i].begin(), words[i].end());suf->insert(words[i], i);}}int f(string prefix, string suffix) {if(prefix.empty() && suffix.empty()) return count-1;//特殊情况auto pre_v = pre->startsWith(prefix);reverse(suffix.begin(), suffix.end());//这儿也需要先翻转auto suf_v = suf->startsWith(suffix);if(!pre_v || !suf_v) return -1; //任意一个为空指针，代表没有找到if(prefix.empty()) return *(suf_v->end()-1);//空指针，返回后缀字典树中的最大权重if(suffix.empty()) return *(pre_v->end()-1);//空指针，返回前缀字典树中的最大权重vector<int>::iterator it1 = pre_v->end()-1, it2 = suf_v->end()-1; while(it1 >= pre_v->begin() && it2 >= suf_v->begin()){//从后往前查找，因为后面的更大if(*it1 == *it2) return *it1;*it1 < *it2 ? --it2 : --it1;}return -1;}
private:Trie *pre;//前缀树Trie *suf;//后缀树int count; //记录树里面的单词个数
};