首页 > 代码库 > 【POJ】1816 Wild Words

【POJ】1816 Wild Words

2024-07-10 00:28:49   215人阅读

DFS+字典树。题目数据很BT。注意控制DFS深度小于等于len。当‘\0‘时，还需判断末尾*。另外，当遇到*时，注意讨论情况。

  1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <cstdlib>  5 #include <vector>  6 #include <algorithm>  7 using namespace std;  8   9 #define TRIEN 28 10  11 typedef struct Trie { 12     vector<int> vc; 13     Trie *next[TRIEN]; 14     Trie() { 15         for (int i=0; i<TRIEN; ++i) 16             next[i] = NULL; 17     } 18 } Trie; 19  20 Trie root; 21 char buf[25]; 22 int nums[100005], nn, len; 23  24 void create(char str[], int in) { 25     int i = 0, id; 26     Trie *p = &root, *q; 27  28     while (str[i]) { 29         if (str[i] == ‘?‘) 30             id = 26; 31         else if (str[i] == ‘*‘) 32             id = 27; 33         else 34             id = str[i] - ‘a‘; 35         ++i; 36         if (p->next[id] == NULL) { 37             q = new Trie(); 38             p->next[id] = q; 39         } 40         p = p->next[id]; 41     } 42     p->vc.push_back(in); 43 } 44  45 void find(Trie *p, int d, int f) { 46     int id; 47     if (d > len) 48         return ; 49     if (buf[d] == ‘\0‘) { 50         int vcn = p->vc.size(); 51         int i; 52         if (vcn) { 53             for (i=0; i<vcn; ++i) 54                 nums[nn++] = p->vc[i]; 55         } 56         if (p->next[27]) 57             find(p->next[27], d, 0); 58         return ; 59     } 60  61     id = buf[d] - ‘a‘; 62     if (p->next[id]) 63         find(p->next[id], d+1, 0); 64     if (p->next[26]) 65         find(p->next[26], d+1, 0); 66     if (p->next[27]) { 67         find(p->next[27], d+1, 1); 68         find(p->next[27], d, 1); 69     } 70     if (f) 71         find(p, d+1, 1); 72 } 73  74 int main() { 75     int n, m, i; 76  77     scanf("%d %d", &n, &m); 78  79     for (i=0; i<n; ++i) { 80         scanf("%s", buf); 81         create(buf, i); 82     } 83  84     while (m--) { 85         scanf("%s", buf); 86         nn = 0; 87         len = strlen(buf); 88         find(&root, 0, 0); 89         if (!nn) { 90             printf("Not match\n"); 91             continue; 92         } 93         sort(nums, nums+nn); 94         printf("%d", nums[0]); 95         for (i=1; i<nn; ++i) 96             if (nums[i] != nums[i-1]) 97                 printf(" %d", nums[i]); 98         printf("\n"); 99     }100 101     return 0;102 }

 


联系
我们