| ||||||||||
| 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 | |||||||||
代码给大家参考一下。dfs中可能有重复计算点,所以输出是要判重。(用指针的trie明显空间比较非指针大些,用时也长些。所以能不用指针尽量不用。)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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator