服装网都有哪些网站,天津做大健康的公司,外包网站开发多少钱,Wordpress百万访问优化trie 树#xff0c;即字典树#xff0c;是一种可以实现 O ( S ) O(S) O(S) 的预处理#xff08; S S S 为所有字符串的长度和#xff09;#xff0c; O ( N ) O(N) O(N)#xff08; N N N 为查询的字符串的长度#xff09;的查询的数据结构。
举个栗子#xff0c;对于…trie 树即字典树是一种可以实现 O ( S ) O(S) O(S) 的预处理 S S S 为所有字符串的长度和 O ( N ) O(N) O(N) N N N 为查询的字符串的长度的查询的数据结构。
举个栗子对于字符串 abcd \texttt{abcd} abcd、 abd \texttt{abd} abd、 bcd \texttt{bcd} bcd、 efg \texttt{efg} efg它的 trie 树如下 那么trie 树的建立、查询操作怎么代码实现呢在此奉上蒟蒻的代码 建立 int trie[maxn][30],cnt[maxn],tot;
//trie[N][r]用来存储Trie树中的子节点节点编号为N它的字符儿子编号为r比如trie[2][3]存储的就是节点编号为2它的一个儿子为d
//cnt[N]存储的是以当前结尾的字符串有多少个tot存储当前共有几个节点
//下标是0的点既是根节点又是空节点
char str[N];
void insert(char *str)
{int p0;//根节点为0for(int i0;str[i];i){int ustr[i]-a;//当前字母子节点if(!trie[p][u]) trie[p][u]tot;//如果当前子节点不存在就创造一个点来存储子节点ptrie[p][u];//让p走到子节点的位置cnt[p];//结尾是p的字符串个数增加}
}查询 int query(char *str)
{int p0;for(int i0;str[i];i){int ustr[i]-a;//当前字母子节点的编号if(!trie[p][u]) return 0;//如果当前字符不存在那么直接返回0ptrie[p][u];//让p走到子节点的位置}return cnt[p];//最后返回以p结尾的字符串个数
}练手板子题
代码如下
#include bits/stdc.h
using namespace std;const int maxn2e65;
int t[maxn][65],cnt[maxn],tot;
char s[maxn];int getn(char x)
{if(xZxA) return x-A;else if(xzxa) return x-a26;else return x-052;
}void insert(char s[])
{int p0,lenstrlen(s);//根节点为0for(int i0;ilen;i){int ugetn(s[i]);//当前字母子节点if(!t[p][u]) t[p][u]tot;//如果当前子节点不存在就创造一个点来存储子节点pt[p][u];//让p走到子节点的位置cnt[p];//结尾是p的字符串个数增加}
}int ask(char s[])
{int p0,lenstrlen(s);for(int i0;ilen;i){int ugetn(s[i]);if(!t[p][u]) return 0;pt[p][u];}return cnt[p];
}int main()
{int T;cinT;while(T--){for(int i0;itot;i)for(int j0;j65;j) t[i][j]0;for(int i0;itot;i) cnt[i]0;tot0;int n,q;cinnq;for(int i1;in;i)cins,insert(s);for(int i1;iq;i)cins,coutask(s)endl;}return 0;
}
