POJ1816 Wild Words

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<algorithm>
  4 #include<cmath>
  5 #include<cstring>
  6 #include<cstdlib>
  7 #include<cctype>
  8 #include<stack>
  9 #include<queue>
 10 #include<vector>
 11 using namespace std;
 12 #define enter puts("")
 13 #define space putchar(' ')
 14 #define Mem(a, x) memset(a, x, sizeof(a))
 15 #define rg register
 16 typedef long long ll;
 17 typedef double db;
 18 const int INF = 0x3f3f3f3f;
 19 const db eps = 1e-8;
 20 const int maxn = 1e5 + 5;
 21 inline ll read()
 22 {
 23   ll ans = 0;
 24   char ch = getchar(), las = ' ';
 25   while(!isdigit(ch)) las = ch, ch = getchar();
 26   while(isdigit(ch)) ans = ans * 10 + ch - '0', ch = getchar();
 27   if(las == '-') ans = -ans;
 28   return ans;
 29 }
 30 inline void write(ll x)
 31 {
 32   if(x < 0) putchar('-'), x = -x;
 33   if(x >= 10) write(x / 10);
 34   putchar(x % 10 + '0');
 35 }
 36 
 37 int n, m;
 38 char s[25];
 39 
 40 int cnt = 0, ch[maxn * 30][30];
 41 vector<int> val[maxn * 30];
 42 
 43 int getnum(char c)
 44 {
 45   if(c == '?') return 26;
 46   else if(c == '*') return 27;
 47   else return c - 'a';
 48 }
 49 void insert(int id, char *s)
 50 {
 51   int m = strlen(s);
 52   for(int i = 0, now = 0; i < m; ++i)
 53     {
 54       int c = getnum(s[i]);
 55       if(!ch[now][c]) ch[now][c] = ++cnt;
 56       now = ch[now][c];
 57       if(i == m - 1) val[now].push_back(id);
 58     }
 59 }
 60 
 61 int len;
 62 vector<int> v;
 63 void dfs(int now, int x)
 64 {
 65   if(ch[now][27])
 66     {
 67       for(int i = x; i <= len; ++i) dfs(ch[now][27], i);
 68     } 
 69   if(x == len)
 70     {
 71       for(int i = 0; i < (int)val[now].size(); ++i) v.push_back(val[now][i]);
 72       return;
 73     }
 74   int c = s[x] - 'a';
 75   if(ch[now][c]) dfs(ch[now][c], x + 1);
 76   if(ch[now][26]) dfs(ch[now][26], x + 1);
 77   return;
 78 }
 79 
 80 int main()
 81 {
 82   n = read(); m = read();
 83   for(int i = 1; i <= n; ++i)
 84     {
 85       scanf("%s", s);
 86       insert(i - 1, s);
 87     }
 88   for(int i = 1; i <= m; ++i)
 89     {
 90       scanf("%s", s);
 91       len = strlen(s);
 92       v.clear();
 93       dfs(0, 0);
 94       if(!v.size()) puts("Not match");
 95       else
 96     {
 97       sort(v.begin(), v.end());
 98       v.resize(unique(v.begin(),v.end()) - v.begin());  //vector可以用unique函数
 99       for(int j = 0; j < (int)v.size(); ++j) write(v[j]), space;
100       enter;
101     }
102     }
103   return 0;
104 }