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

代码给大家参考一下。dfs中可能有重复计算点,所以输出是要判重。(用指针的trie明显空间比较非指针大些,用时也长些。所以能不用指针尽量不用。)

Posted by alpc47 at 2011-10-12 21:19:32 on Problem 1816 and last updated at 2011-10-12 21:19:55
In Reply To:Trie + dfs 第一次在Trie树上进行DFS,易错点是被匹配的串中可能有相同的,dfs中找到匹配的串后应继续找,不能退出! Posted by:alpc47 at 2009-08-07 18:09:50
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int M = 28;
int n, m;
struct INT { int v; INT * next; };
struct Node { Node * c[M]; INT * id;} * f; 
char s[M];

void trie_add(char * s, int id)
{
     Node * p = f;
     int i, x;
     for (i=0; s[i]; i++)
     {
          if (s[i]=='?') x = 26;
          else if (s[i]=='*') x = 27;
          else  x = s[i]-'a';
          if (p->c[x]==NULL)
          {
               Node * tmp = new Node();
               memset(tmp->c, 0, sizeof(tmp->c));
               tmp->id = 0;
               p->c[x] = tmp;
          }
          p = p->c[x];
     }
     INT * tmp = new INT();
     tmp->v = id;
     tmp->next = p->id;
     p->id = tmp;
}

const int N =100010;
int a[N], la;
int ls;

void l_dfs(Node * p, int x, int isStar)
{
     if (x == ls-1)
     {
           INT * tmp = p->id;
           while (tmp)
           {
                 a[la++] = tmp->v;
                 tmp = tmp->next;
           }
     }
     if (p->c[27]) l_dfs(p->c[27], x, 0); 
     if (!s[x+1]) return;
     if (p->c[s[x+1]-'a']) l_dfs(p->c[s[x+1]-'a'], x+1, 0);
     if (p->c[26]) l_dfs(p->c[26], x+1, 0);
     if (p->c[27]) l_dfs(p->c[27], x+1, 1);
     if (isStar) l_dfs(p, x+1, 1);
}

int main()
{
    //freopen("c.in","r",stdin);
    f = new Node();
    memset(f->c, 0, sizeof(f->c));
    f->id = 0;
    
    scanf("%d%d", &n, &m);   
    int i;
    for (i=0; i<n; i++)
    {
          scanf("%s", s);
          trie_add(s, i);
    }
    while (m--)
    {
          scanf("%s", s);
          ls = strlen(s);
          la = 0;
          l_dfs(f, -1, 0);
          if (la == 0) { printf("Not match\n"); continue; }
          sort(a, a+la);
          printf("%d", a[0]);
          for (i=1; i<la; i++) if (a[i]!=a[i-1]) printf(" %d", a[i]);
          printf("\n");
    }
    //while(1);
    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