space ret sam mod eof feature pac push struct
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 70290 Accepted Submission(s): 23917
题意:给出一个字典和一个模式串,问模式串中出现几个字典中的单词
代码:
- ////#include "bits/stdc++.h"
- #include "cstdio"
- #include "map"
- #include "set"
- #include "cmath"
- #include "queue"
- #include "vector"
- #include "string"
- #include "cstring"
- #include "time.h"
- #include "iostream"
- #include "stdlib.h"
- #include "algorithm"
- #define db double
- #define ll long long
- //#define vec vector<ll>
- #define Mt vector<vec>
- #define ci(x) scanf("%d",&x)
- #define cd(x) scanf("%lf",&x)
- #define cl(x) scanf("%lld",&x)
- #define pi(x) printf("%d\n",x)
- #define pd(x) printf("%f\n",x)
- #define pl(x) printf("%lld\n",x)
- #define rep(i, x, y) for(int i=x;i<=y;i++)
- const int N = 1e6 + 5;
- const int mod = 1e9 + 7;
- const int MOD = mod - 1;
- const db eps = 1e-18;
- const db PI = acos(-1.0);
- using namespace std;
- const int M = 26;
- queue<int> q;
- vector<string> vec;
- bool vis[N];
- struct Trie {
- int trieN;
- int ch[N][M], val[N], fail[N];
- void init() {
- memset(vis,0,sizeof(vis));
- trieN = -1;
- newnode();
- }
- int newnode() {
- memset(ch[++trieN], 0, sizeof(ch[0]));
- val[trieN] = fail[trieN] = 0;
- return trieN;
- }
- void insert(const string &str, int index) {
- int cur = 0;
- for (int i = 0;str[i];i++) {
- int d = str[i] - ‘a‘;
- if (!ch[cur][d])
- ch[cur][d] = newnode();
- cur = ch[cur][d];
- }
- if (val[cur]) vis[index] = 1;
- else val[cur] = index;
- }
- void build() {
- for (int i = 0;i < M;i++) {
- if (ch[0][i])
- q.push(ch[0][i]);
- }
- while (!q.empty()) {
- int cur = q.front(); q.pop();
- for (int i = 0;i < M;i++) {
- int &next = ch[cur][i];
- if (next) {
- fail[next] = ch[fail[cur]][i];
- q.push(next);
- }
- else next = ch[fail[cur]][i];
- }
- }
- }
- void query(const string &str) {
- int cur = 0, tmp;
- for (int i = 0;str[i];i++) {
- int d = str[i] - ‘a‘;
- tmp = cur = ch[cur][d];
- while (tmp && ~val[tmp]) {
- if (val[tmp] != -1) vis[val[tmp]] = 1;
- val[tmp] = -1;
- tmp = fail[tmp];
- }
- }
- }
- }ac;
- int main(){
- ios::sync_with_stdio(false);
- cin.tie(0);
- int t;
- cin >> t;
- while(t--){
- ac.init(); //初始化
- int n;
- string str;
- cin >> n;
- vec.resize(n+1);
- for(int i = 1;i <= n;i++){
- cin >> vec[i];
- ac.insert(vec[i],i);
- }
- ac.build();
- cin>>str;
- ac.query(str); //查询是否在str里出现过
- int ans=0;
- for(int i = 1;i <= n;i++){
- if (vis[i]) ans++;
- }
- pi(ans);
- }
- return 0;
- }
HDU 2222 AC自动机(模版题)
space ret sam mod eof feature pac push struct
原文:http://www.cnblogs.com/mj-liylho/p/8010639.html
来源: http://www.bubuko.com/infodetail-2421984.html