当前位置：首页 > news >正文

HDU 2222 Keywords Search（AC自动机）

news 来源：原创 2024/5/17 13:46:20

裸的AC自动机，

这倒题不能使用静态数组模拟建树的过程，10000*50*26这样会爆内存，所以使用指针，使用结构体动态分配new

这个可以用来做模板了

  1 //#pragma comment(linker, "/STACK:1677721600")
  2 #include <map>
  3 #include <set>
  4 #include <stack>
  5 #include <queue>
  6 #include <cmath>
  7 #include <ctime>
  8 #include <vector>
  9 #include <cstdio>
 10 #include <cctype>
 11 #include <cstring>
 12 #include <cstdlib>
 13 #include <iostream>
 14 #include <algorithm>
 15 using namespace std;
 16 #define INF 0x3f3f3f3f
 17 #define inf (-((LL)1<<40))
 18 #define lson k<<1, L, (L + R)>>1
 19 #define rson k<<1|1,  ((L + R)>>1) + 1, R
 20 #define mem0(a) memset(a,0,sizeof(a))
 21 #define mem1(a) memset(a,-1,sizeof(a))
 22 #define mem(a, b) memset(a, b, sizeof(a))
 23 #define FIN freopen("in.txt", "r", stdin)
 24 #define FOUT freopen("out.txt", "w", stdout)
 25 #define rep(i, a, b) for(int i = a; i <= b; i ++)
 26 #define dec(i, a, b) for(int i = a; i >= b; i --)
 27 
 28 template<class T> T MAX(T a, T b) { return a > b ? a : b; }
 29 template<class T> T MIN(T a, T b) { return a < b ? a : b; }
 30 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }
 31 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }
 32 
 33 //typedef __int64 LL;
 34 typedef long long LL;
 35 const int MAXN = 10000 + 100;
 36 const int MAXM = 1000010;
 37 const double eps = 1e-8;
 38 LL MOD = 1000000007;
 39 
 40 const int SIGMA_SIZE = 26;
 41 const int MAX_LEN = 52;
 42 
 43 struct Node {
 44     int val;
 45     Node *ch[SIGMA_SIZE];
 46     Node *f, *last;
 47     Node() {
 48         rep (i, 0, SIGMA_SIZE - 1) {
 49             ch[i] = NULL;
 50         }
 51         f = last = NULL;
 52         val = 0;//非结点
 53     }
 54 };
 55 
 56 struct ACMachine {
 57     int node_cnt;
 58     Node *head;
 59     queue<Node*>q;
 60 
 61     void init() {
 62         node_cnt = 0;
 63         head = new Node();
 64     }
 65     int get_idx(char ch) {
 66         return ch - 'a';
 67     }
 68     void insert_to_tree(char *str) {
 69         Node *u = head;
 70         for(int i = 0; str[i]; i ++) {
 71             int c = get_idx(str[i]);
 72             if(!u->ch[c]) {
 73                 u->ch[c] = new Node();
 74             }
 75             u = u->ch[c];
 76         }
 77         u->val ++;
 78     }
 79     void getFail() {
 80         q.push(head);
 81         while(!q.empty()) {
 82             Node *r = q.front(); q.pop();
 83             rep (c, 0, SIGMA_SIZE - 1) {
 84                 Node *u = r->ch[c];
 85                 if(u == NULL) {
 86                     if(r != head) r->ch[c] = r->f->ch[c];
 87                     continue;
 88                 }
 89                 q.push(u);
 90                 if(r == head) { u->f = head; continue; }
 91                 Node *v = r->f;
 92                 while(v && v->ch[c] == NULL) v = v->f;
 93                 u->f = v == NULL ? head : v->ch[c];
 94                 u->last = u->f->val ? u->f : u->f->last;
 95             }
 96         }
 97     }
 98     int findAns(char *T) {
 99         int n = strlen(T), ans = 0;
100         Node *u = head;
101         rep (i, 0, n - 1) {
102             int c = get_idx(T[i]);
103             u = u->ch[c];
104             if(!u) u = head;
105             Node *v = u;
106             while(v != NULL) {
107                 if(v->val >= 0) {
108                     ans += v->val;
109                     v->val = -1;
110                 }
111                 else break;
112                 v = v->last;
113             }
114         }
115         return ans;
116     }
117 }acm;
118 
119 int t, n;
120 char str[MAXM];
121 
122 int main()
123 {
124 //    FIN;
125     cin >> t;
126     while(t--) {
127         acm.init();
128         scanf("%d%*c", &n);
129         rep (i, 1, n) {
130             scanf("%s", str);
131             acm.insert_to_tree(str);
132         }
133         scanf("%s", str);
134         acm.getFail();
135         cout << acm.findAns(str) << endl;
136     }
137     return 0;
138 }