zoj 3228 Searching the String(trie)

zoj 3228 Searching the String(trie)

题目：​​1输出统计的结果。考虑到内存，用数组不用指针。这种用数组写出的trie树可以过。

#include #include#includeusing namespace std;const int nn=26,maxn=1e5+10;int N,top,root,tp;char str[maxn],keyword[10];struct node{ int next[nn],c[2]; int loc;}tree[6*maxn];int newnode(){ for(int i=0;i

代码中的here: 用length存储strlen的结果，不然在循环中反复计算就超时了。（自己当时就犯这种错误）

本来也想用AC解决的，结果中间有一个错误不理解也改不了。。。贴上来，说不定哪天自己就看出来了：

#include #include#include#include using namespace std;const int nn=26,maxn=1e5+10;char str[maxn],word[15];struct node{ int pos,len,id[2]; node *next[27],*fail; node(){ pos=-1; id[0]=id[1]=len=0; fail=NULL; memset(next,0,sizeof(next)); }};node *root,*que[maxn*6];int *question[maxn]; //因为要保存值，所以要设成指针数组. 指针只读不写！void insert(char *s,int tag,int dex){ node *p=root; int length=strlen(s); for(int i=0;inext[s[i]-'a']==0) p->next[s[i]-'a']=new node(); p=p->next[s[i]-'a']; } p->len=length; question[dex]=&(p->id[tag]);}void build_fail(){ int head=0,tail=0; que[tail++]=root; while(headnext[i]){ node *f=p->fail; while(f){ if(f->next[i]){ p->next[i]->fail=f->next[i]; //对应图 break; } f=f->fail; } if(f==root)f->next[i]->fail=root; que[tail++]=p->next[i]; } } }}void find(char *s){ //fail指针，KMP都是紧密相连的 int length=strlen(s); node *p=root; for(int i=0;inext[k]==NULL&&p!=root)p=p->fail; /*p=p->next[k]; //this sentence is wrong, it make program stop ******************* if(!p)p=root; //调整目标串的对应起点 node *tmp=p; while(tmp!=root){ //回到根节点说明就已经把能找的都找完了，如果一开始tmp就等于root，那么起点就是长串的第一个字符，顺推~ if(tmp->len>0){ tmp->id[0]++; if(tmp->pos==-1 || i-tmp->pos>=tmp->len){ //i-tmp->pos>=tmp->len not > tmp->id[1]++; tmp->pos=i; //更新 } } tmp=tmp->fail; }*/ }}void del(node *p){ if(p==NULL)return ; for(int i=0;inext[i]); delete p;}int main(){ freopen("cin.txt","r",stdin); int ca=1; while(cin>>str){ root=new node(); int n,tag; scanf("%d",&n); for(int i=0;i

错误：0x3C0000005

----------------------------------------------------------------------------------------------------------------------------------------

2016. 03 .31

插入的思想都不一样，当然出现各种错误了。应该是把长串上的各个连续子串都放进trie树。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。