Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
我哪里还有错啊,望达人不吝赐教,或给些数据In Reply To:如果在Trie里定义一个vector用来保存重复编号会不会超内存啊 Posted by:foreverlin at 2009-01-24 21:45:16 #include<iostream> #include<vector> using namespace std; //我的做法 //首先对其进行插入处理 //用一个整形容器存放id,这样就避免了重复出现的问题 //然后对进行dfs //分三种情况考虑如果是常规和?那么深入dfs //如果是*如果*所在位置有编号,那么这些都是符合的 //然后做循环,每个位置都进行深搜 char a[21]; typedef struct Trie { vector<int>c;//代表模式的编号 Trie *next[28];//其中26标记问号,27标记※号 }Trie; Trie node[100001]; Trie *s,*t,root; int pos; int n,m; int d[100000],lend; void build(Trie &head) { int i; for(i=0;i<28;i++) { head.next[i]=NULL; } // head.c=-1; pos=0; } void insert(Trie &head,char *b,int num) { int i,j,k,flag,len=strlen(b); s=&head; flag=0; for(i=0;i<len;i++) { if(b[i]=='?') { if(s->next[26]==NULL) { j=i;flag=1;break; } s=s->next[26]; } else if(b[i]=='*') { if(s->next[27]==NULL) { j=i;flag=1;break; } s=s->next[27]; } else { if(s->next[b[i]-'a']==NULL) { j=i;flag=1;break; } s=s->next[b[i]-'a']; } } // cout<<"j="<<j<<endl; for(i=j;i<len;i++) { t=&node[pos++]; // cout<<"pos="<<pos<<" "; // cout<<"i="<<i<<endl; for(k=0;k<28;k++) { t->next[k]=NULL; } // t->c=-1; if(b[i]=='?') { s->next[26]=t; // cout<<" i="<<i<<endl; } else if(b[i]=='*') { s->next[27]=t; // cout<<"i= "<<i<<endl; } else { s->next[b[i]-'a']=t; // cout<<"i="<<i<<endl; } s=t; } // s->c=num; (s->c).push_back(num); // cout<<"num="<<num<<endl; } void dfs(Trie *head,int temp,int len) { int i,j,k,r,x; if(temp==len-1) { if(head->next[a[temp]-'a']!=NULL) { // x=head->next[a[temp]-'a']->c; s=head->next[a[temp]-'a']; for(i=0;i<(s->c).size();i++) { x=(s->c)[i]; if(x!=-1)d[lend++]=x; // cout<<"endx="<<x<<endl; } if(head->next[a[temp]-'a']->next[27]!=NULL) { s=head->next[a[temp]-'a']->next[27]; for(i=0;i<(s->c).size();i++) { x=(s->c)[i]; if(x!=-1) { d[lend++]=x; } } } } if(head->next[26]!=NULL) { s=head->next[26]; for(i=0;i<(s->c).size();i++) { x=(s->c)[i]; if(x!=-1)d[lend++]=x; // cout<<"endx="<<x<<endl; } } if(head->next[27]!=NULL) { s=head->next[27]; for(i=0;i<(s->c).size();i++) { x=(s->c)[i]; if(x!=-1)d[lend++]=x; } // cout<<"endx="<<x<<endl; } // system("pause"); return ; } if(head->next[a[temp]-'a']!=NULL) { // cout<<"case 1:"<<"a["<<temp<<"]="<<a[temp]<<endl; dfs(head->next[a[temp]-'a'],temp+1,len); } if(head->next[26]!=NULL) { // cout<<"case ?:"<<"a["<<temp<<"]="<<a[temp]<<endl; dfs(head->next[26],temp+1,len); } if(head->next[27]!=NULL) { // cout<<"case *:"<<"a["<<temp<<"]="<<a[temp]<<endl; while(head->next[27]!=NULL) { if(!(head->next[27]->c).empty()) { s=head->next[27]; for(i=0;i<(s->c).size();i++) { x=(s->c)[i]; d[lend++]=x; } // cout<<"endx="<<head->next[27]->c<<endl; } head=head->next[27]; } for(i=temp;i<len;i++)//为什么要从temp开始而不是temp+1呢,是因为*可以什么都不代替直接略过 { dfs(head,i,len); } } return ; } int main() { int i,j,k,r,len; while(scanf("%d%d",&n,&m)!=EOF) { build(root); for(i=0;i<n;i++) { scanf("%s",a); insert(root,a,i); } // cout<<"pos="<<pos<<endl;system("pause"); for(i=0;i<m;i++) { scanf("%s",a); len=strlen(a); lend=0; dfs(&root,0,len); if(lend==0) { printf("Not match\n"); continue; } printf("%d",d[0]); for(j=1;j<lend;j++) { printf(" %d",d[j]); } printf("\n"); } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator