字符串集合的保存

1. 笔记
多个单词匹配一个句子。将单词组织成树，查询时只需要从根结点到叶结点一个一个字母地比较即可。
假设有\(n\)个单词，单词最长为\(l\)。如果一个单词一个单词地暴力匹配，最坏情况（所有单词都长为\(l\)，且只有最后一位不一样）下复杂度为\(O(nl)\)。如果用Trie保存查询，则无论如何复杂度都为\(O(l)\)。

2. 代码
const int maxnodeTrie的最大结点数
const int sigma_size字符集大小+1
int Trie::get_index(char c)获取字符c在字符集中的编号
void Trie::Insert(const char s[],int val)向Trie中插入权值为val的字符串s
void Trie::Query(const char s[],int len,vector<int>& ans)查询字符串s的前len位有几个前缀在Trie中，并把找到的单词的权值记录在ans中

Trie结构体需在静态空间或堆中声明

/* 变量声明： int ch[int i][int j] 与编号i的结点以编号为j的字符为边相连的儿子结点的编号 int val[int i] 编号为i的结点的权值 int sz Trie的结点总数 备注： 已测试 2018/09/03 */ const int maxnode=4e5+5,sigma_size=27; struct Trie { int ch[maxnode][sigma_size],val[maxnode]; int sz; void clear(){sz=1;memset(ch[0],0,sizeof ch[0]);} int get_index(char c){return c-'a'+1;} void Insert(const char s[],int value) { int u,e,v; for(u=0;*s;++s,u=v) { e=get_index(*s);v=ch[u][e]; if(!v) { memset(ch[sz],0,sizeof ch[sz]);val[sz]=0; ch[u][e]=v=sz++; } } val[u]=value; } void Query(const char s[],int len,vector<int>& ans) { int u,e,v; for(u=0;(*s)&&len&&(v=ch[u][get_index(*s)]);u=v,++s,--len)if(val[v])ans.push_back(val[v]); } };

转载于:https://www.cnblogs.com/maoruimas/p/9572288.html

原文链接：https://blog.csdn.net/weixin_30342827/article/details/97929975

本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。