【HDOJ】2279 File Search Tool

显然适用字典树建树，串长和模式串都很小，所以直接递归搜索。同时，适用bk标记当前的查询次数（排除不同模式的多次查询成功，如*t*）。需要主要的是，居然存在同名文件！！！。

 /* 2279 */

 #include <iostream>

 #include <string>

 #include <map>

 #include <queue>

 #include <set>

 #include <stack>

 #include <vector>

 #include <deque>

 #include <algorithm>

 #include <cstdio>

 #include <cmath>

 #include <ctime>

 #include <cstring>

 #include <climits>

 #include <cctype>

 #include <cassert>

 #include <functional>

 using namespace std;

 #define rep(i, a, n)     for (int i=a;i<n;++i)

 #define per(i, a, n)     for (int i=n-1;i>=a;--i)

 #define pb                 push_back

 #define mp                 make_pair

 #define all(x)             (x).begin(),(x).end()

 #define SZ(x)             ((int)(x).size())

 #define lson            l, mid, rt<<1

 #define rson            mid+1, r, rt<<1|1

 typedef struct node_t {

     int in;

     int c;

     int next[];

 } node_t;

 const int maxl = ;

 const int maxn = ;

 node_t nd[maxn*maxl];

 char s[maxl], d[maxl];

 int dl, sl;

 int L = maxn*maxl, bk;

 int n, m, ans;

 void init() {

     memset(nd, , sizeof(node_t)*L);

     L = bk = ;

 }

 void insert() {

     int i = , id;

     int p = , q;

     while (s[i]) {

         id = s[i] - 'a';

         q = nd[p].next[id];

         if (q == )

             q = nd[p].next[id] = L++;

         p = q;

         ++i;

     }

     ++nd[p].c;

 }

 void search(int p, int l) {

     if (l == dl) {

         if (nd[p].c && nd[p].in!=bk) {

             ans += nd[p].c;

             nd[p].in = bk;

         }

         return ;

     }

     if (d[l] == '?') {

         for (int i=; i<; ++i)

             if (nd[p].next[i])

                 search(nd[p].next[i], l+);

     } else if (d[l] == '*') {

         search(p, l+);

         for (int i=; i<; ++i)

             if (nd[p].next[i])

                 search(nd[p].next[i], l);

     } else {

         int id = d[l] - 'a';

         if (nd[p].next[id])

             search(nd[p].next[id], l+);

     }

 }

 void handle() {

     int i = ;

     sl = strlen(s);

     dl = ;

     while () {

         while (s[i]=='*'&&s[i+]=='*')

             ++i;

         if (i >= sl)

             break;

         d[dl++] = s[i++];

     }

     d[dl] = '\0';

 }

 int main() {

     int i, j, k;

     #ifndef ONLINE_JUDGE

         freopen("data.in", "r", stdin);

         freopen("data.out", "w", stdout);

     #endif

     while (scanf("%d %d",&n,&m)!=EOF) {

         init();

         for (i=; i<n; ++i) {

             scanf("%s", s);

             insert();

         }

         while (m--) {

             scanf("%s", s);

             handle();

             ans = ;

             search(, );

             ++bk;

             if (ans)

                 printf("%d\n", ans);

             else

                 puts("Not match");

         }

     }

     #ifndef ONLINE_JUDGE

         printf("time = %d.\n", (int)clock());

     #endif

     return ;

 }