本文共 2155 字，大约阅读时间需要 7 分钟。
显然适用字典树建树，串长和模式串都很小，所以直接递归搜索。同时，适用bk标记当前的查询次数（排除不同模式的多次查询成功，如*t*）。需要主要的是，居然存在同名文件！！！。
1 /* 2279 */ 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 using namespace std; 20 21 #define rep(i, a, n) for (int i=a;i =a;--i) 23 #define pb push_back 24 #define mp make_pair 25 #define all(x) (x).begin(),(x).end() 26 #define SZ(x) ((int)(x).size()) 27 #define lson l, mid, rt<<1 28 #define rson mid+1, r, rt<<1|1 29 30 typedef struct node_t { 31 int in; 32 int c; 33 int next[26]; 34 } node_t; 35 36 const int maxl = 21; 37 const int maxn = 10001; 38 node_t nd[maxn*maxl]; 39 char s[maxl], d[maxl]; 40 int dl, sl; 41 int L = maxn*maxl, bk; 42 int n, m, ans; 43 44 void init() { 45 memset(nd, 0, sizeof(node_t)*L); 46 L = bk = 1; 47 } 48 49 void insert() { 50 int i = 0, id; 51 int p = 0, q; 52 53 while (s[i]) { 54 id = s[i] - 'a'; 55 q = nd[p].next[id]; 56 if (q == 0) 57 q = nd[p].next[id] = L++; 58 p = q; 59 ++i; 60 } 61 ++nd[p].c; 62 } 63 64 void search(int p, int l) { 65 if (l == dl) { 66 if (nd[p].c && nd[p].in!=bk) { 67 ans += nd[p].c; 68 nd[p].in = bk; 69 } 70 return ; 71 } 72 73 if (d[l] == '?') { 74 for (int i=0; i<26; ++i) 75 if (nd[p].next[i]) 76 search(nd[p].next[i], l+1); 77 78 } else if (d[l] == '*') { 79 search(p, l+1); 80 for (int i=0; i<26; ++i) 81 if (nd[p].next[i]) 82 search(nd[p].next[i], l); 83 84 } else { 85 int id = d[l] - 'a'; 86 if (nd[p].next[id]) 87 search(nd[p].next[id], l+1); 88 89 } 90 } 91 92 void handle() { 93 int i = 0; 94 95 sl = strlen(s); 96 dl = 0; 97 while (1) { 98 while (s[i]=='*'&&s[i+1]=='*') 99 ++i;100 if (i >= sl)101 break;102 d[dl++] = s[i++];103 }104 d[dl] = '\0';105 }106 107 int main() {108 int i, j, k;109 110 #ifndef ONLINE_JUDGE111 freopen("data.in", "r", stdin);112 freopen("data.out", "w", stdout);113 #endif114 115 while (scanf("%d %d",&n,&m)!=EOF) {116 init();117 for (i=0; i
转载于:https://www.cnblogs.com/bombe1013/p/4507102.html