例题: HDU - 2222
给 \(n\) 个字符串, 一个模式串. 然后输出匹配次数.
代码
- #include <bits/stdc++.h>
- #define FOPI freopen("in.txt", "r", stdin)
- #define FOPO freopen("out.txt", "w", stdout)
- #define FOR(i,x,y) for (int i = x; i <= y; i++)
- #define ROF(i,x,y) for (int i = x; i>= y; i--)
- using namespace std;
- typedef long long LL;
- struct Trie
- {
- int next[500010][26], fail[500010], end[500010];
- int root, L;
- int newnode()
- {
- FOR(i, 0, 26-1) next[L][i] = -1;
- end[L++] = 0;
- return L-1;
- }
- void init() { L = 0; root = newnode(); }
- void insert(char buf[])
- {
- int len = strlen(buf), now = root;
- FOR(i, 0, len-1)
- {
- if (next[now][buf[i] - 'a'] == -1)
- next[now][buf[i] - 'a'] = newnode();
- now = next[now][buf[i] - 'a'];
- }
- end[now]++;
- }
- void build()
- {
- queue<int> Q;
- fail[root] = root;
- FOR(i, 0, 26-1)
- if (next[root][i] == -1) next[root][i] = root;
- else
- {
- fail[next[root][i]] = root;
- Q.push(next[root][i]);
- }
- while(!Q.empty())
- {
- int now = Q.front();
- Q.pop();
- FOR(i, 0, 26-1)
- if (next[now][i] == -1)
- next[now][i] = next[fail[now]][i];
- else
- {
- fail[next[now][i]] = next[fail[now]][i];
- Q.push(next[now][i]);
- }
- }
- }
- int query(char buf[])
- {
- int len = strlen(buf);
- int now = root;
- int res = 0;
- FOR(i, 0, len-1)
- {
- now = next[now][buf[i]-'a'];
- int temp = now;
- while(temp != root)
- {
- res += end[temp];
- end[temp] = 0;
- temp = fail[temp];
- }
- }
- return res;
- }
- // void debug()
- // {
- // FOR(i, 0, L-1)
- // {
- // printf("id = =,fail = =,end = =,chi = [", i, fail[i], end[i]);
- // FOR(j, 0, 26-1) printf("-", next[i][j]);
- // printf("]\n");
- // }
- // }
- };
- char buf[1000010];
- Trie ac;
- int t, n;
- int main()
- {
- scanf("%d", &t);
- FOR(ca, 1, t)
- {
- scanf("%d", &n);
- ac.init();
- FOR(i, 0, n-1)
- {
- scanf("%s", buf);
- ac.insert(buf);
- }
- ac.build();
- scanf("%s", buf);
- printf("%d\n", ac.query(buf));
- }
- }
来源: http://www.bubuko.com/infodetail-3068912.html