首页 > 代码库 > 前缀 树
前缀 树
已哭瞎。 搞了2个多小时的错误居然是在 没有初始化。。。。。。。。。。。。教训：每个例子一定要考虑到初始化问题。！
每个节点存了一个数组 该数组记录的有26个大小 0-25分别表示记录表示‘a‘-‘z‘。一个节点数组的单位记录的是下一个节点的索引即第几个节点。 节点数组记录了
他的所有子节点在哪里和以及子节点的字符是什么。本节点没有记录自己的字符。
适用于 多个字符串。减少枚举量
#include<cstdio>#include<iostream>#include<cstring>using namespace std;#define maxnode 500000#define sigma_dize 27#define Mod 20071027int cnt;char str[300005],word[105];int num[300005];struct Trie{ int ch[maxnode][sigma_dize]; int val[maxnode]; int size; void Init() { size=1;memset(ch[0],0,sizeof(ch[0])); } int idx(char c) { return c-‘a‘; } void insert(char *s,int v) { int u=0; int len=strlen(s); for(int i=0;i<len;i++) { int c=idx(s[i]); if(!ch[u][c]) { memset(ch[size],0,sizeof(ch[size])); val[size]=0; ch[u][c]=size++; } u=ch[u][c]; } val[u]=v; } void search(char * s,int start) { int u=0;num[start]=0; int len=strlen(s); for(int i=start;i<len;i++) { int c=idx(s[i]); if(ch[u][c]==0) return; u=ch[u][c]; if(val[u]) num[start]=(num[i+1]+num[start])%Mod; } }};Trie curTire;int main(void){ int s,h=1; while(scanf("%s",str)!=EOF) { curTire.Init(); cin>>s; while(s--) { scanf("%s",word); curTire.insert(word,1); } int len=strlen(str); memset(num,0,sizeof(num)); num[len]=1; cnt=0; for(int i=len-1;i>=0;i--) curTire.search(str,i); printf("Case %d: %d\n",h++, num[0]); } return 0;}
前缀 树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。