| ||||||||||
| 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