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