Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

我哪里还有错啊,望达人不吝赐教,或给些数据

Posted by foreverlin at 2009-01-24 22:53:13 on Problem 1816
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator