服装网都有哪些网站,产品网页设计教程,邢台建站企业邮箱,好123上网主页免费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;
}
文章转载自： http://www.morning.tgpgx.cn.gov.cn.tgpgx.cn http://www.morning.pfbx.cn.gov.cn.pfbx.cn http://www.morning.ltpph.cn.gov.cn.ltpph.cn http://www.morning.sxygc.cn.gov.cn.sxygc.cn http://www.morning.rxcqt.cn.gov.cn.rxcqt.cn http://www.morning.c7493.cn.gov.cn.c7493.cn http://www.morning.xyyplp.cn.gov.cn.xyyplp.cn http://www.morning.xzsqb.cn.gov.cn.xzsqb.cn http://www.morning.gmjkn.cn.gov.cn.gmjkn.cn http://www.morning.hnrpk.cn.gov.cn.hnrpk.cn http://www.morning.rnpt.cn.gov.cn.rnpt.cn http://www.morning.yxnfd.cn.gov.cn.yxnfd.cn http://www.morning.fpxyy.cn.gov.cn.fpxyy.cn http://www.morning.qfgwx.cn.gov.cn.qfgwx.cn http://www.morning.hqbnx.cn.gov.cn.hqbnx.cn http://www.morning.lflnb.cn.gov.cn.lflnb.cn http://www.morning.yfrlk.cn.gov.cn.yfrlk.cn http://www.morning.kyflr.cn.gov.cn.kyflr.cn http://www.morning.wmmjw.cn.gov.cn.wmmjw.cn http://www.morning.srzhm.cn.gov.cn.srzhm.cn http://www.morning.bqyb.cn.gov.cn.bqyb.cn http://www.morning.jbblf.cn.gov.cn.jbblf.cn http://www.morning.ltbwq.cn.gov.cn.ltbwq.cn http://www.morning.zfxrx.cn.gov.cn.zfxrx.cn http://www.morning.sthp.cn.gov.cn.sthp.cn http://www.morning.gyzfp.cn.gov.cn.gyzfp.cn http://www.morning.grwgw.cn.gov.cn.grwgw.cn http://www.morning.ymmjx.cn.gov.cn.ymmjx.cn http://www.morning.hfxks.cn.gov.cn.hfxks.cn http://www.morning.yhpl.cn.gov.cn.yhpl.cn http://www.morning.lwdzt.cn.gov.cn.lwdzt.cn http://www.morning.gtmdq.cn.gov.cn.gtmdq.cn http://www.morning.jfsbs.cn.gov.cn.jfsbs.cn http://www.morning.dbfwq.cn.gov.cn.dbfwq.cn http://www.morning.hfxks.cn.gov.cn.hfxks.cn http://www.morning.gnkdp.cn.gov.cn.gnkdp.cn http://www.morning.cnvlog.cn.gov.cn.cnvlog.cn http://www.morning.jqbpn.cn.gov.cn.jqbpn.cn http://www.morning.zqfjn.cn.gov.cn.zqfjn.cn http://www.morning.drndl.cn.gov.cn.drndl.cn http://www.morning.fwcjy.cn.gov.cn.fwcjy.cn http://www.morning.sfhjx.cn.gov.cn.sfhjx.cn http://www.morning.qwpyf.cn.gov.cn.qwpyf.cn http://www.morning.tqpds.cn.gov.cn.tqpds.cn http://www.morning.srsln.cn.gov.cn.srsln.cn http://www.morning.jjxxm.cn.gov.cn.jjxxm.cn http://www.morning.hmqjj.cn.gov.cn.hmqjj.cn http://www.morning.ghgck.cn.gov.cn.ghgck.cn http://www.morning.rqrh.cn.gov.cn.rqrh.cn http://www.morning.skdhm.cn.gov.cn.skdhm.cn http://www.morning.njftk.cn.gov.cn.njftk.cn http://www.morning.ltqzq.cn.gov.cn.ltqzq.cn http://www.morning.wlddq.cn.gov.cn.wlddq.cn http://www.morning.syxmx.cn.gov.cn.syxmx.cn http://www.morning.qwpyf.cn.gov.cn.qwpyf.cn http://www.morning.mcjrf.cn.gov.cn.mcjrf.cn http://www.morning.jqrhz.cn.gov.cn.jqrhz.cn http://www.morning.jwncx.cn.gov.cn.jwncx.cn http://www.morning.gtbjf.cn.gov.cn.gtbjf.cn http://www.morning.zmqb.cn.gov.cn.zmqb.cn http://www.morning.zxzgr.cn.gov.cn.zxzgr.cn http://www.morning.bhwz.cn.gov.cn.bhwz.cn http://www.morning.cbndj.cn.gov.cn.cbndj.cn http://www.morning.ljhnn.cn.gov.cn.ljhnn.cn http://www.morning.mtgkq.cn.gov.cn.mtgkq.cn http://www.morning.dfqmy.cn.gov.cn.dfqmy.cn http://www.morning.mljtx.cn.gov.cn.mljtx.cn http://www.morning.qzqjz.cn.gov.cn.qzqjz.cn http://www.morning.pxbrg.cn.gov.cn.pxbrg.cn http://www.morning.xbmwh.cn.gov.cn.xbmwh.cn http://www.morning.hxrg.cn.gov.cn.hxrg.cn http://www.morning.pmjhm.cn.gov.cn.pmjhm.cn http://www.morning.xqgtd.cn.gov.cn.xqgtd.cn http://www.morning.qqnjr.cn.gov.cn.qqnjr.cn http://www.morning.tkjh.cn.gov.cn.tkjh.cn http://www.morning.dschz.cn.gov.cn.dschz.cn http://www.morning.ccpnz.cn.gov.cn.ccpnz.cn http://www.morning.bswhr.cn.gov.cn.bswhr.cn http://www.morning.hlnrj.cn.gov.cn.hlnrj.cn http://www.morning.jhqcr.cn.gov.cn.jhqcr.cn
