#include<bits/stdc++.h>using namespace std;const int maxn = 1e7 + 5;const int MAX = 10000000;int cnt;struct node{ node *next[26]; node *fail; int sum;};node *root;char key[70];node *q[MAX];int head,tail;node *newnode;char pattern[maxn];int N;void Insert(char s[]) //建trie树 { node *p = root; for(int i = 0; s[i]; i++) //注意中间的东西，s[i]不为空时。 { int x = s[i] - 'a'; if(p->next[x] == NULL) { newnode = new node; //先用newnode指针把地址建好，然后在31行直接传到p->next[x] for(int j=0;j<26;j++) newnode->next[j] = NULL; newnode->sum = 0; //记录是几个单词的结尾 newnode->fail = NULL; p->next[x] = newnode; } p = p->next[x]; } p->sum++;}void build_fail_pointer(){ head = 0; tail = 1; q[head] = root; //手动模拟队列 node *p; node *temp; while(head < tail) { temp = q[head++]; for(int i = 0; i <= 25; i++) { if(temp->next[i] != NULL) { if(temp == root) //root的fail指针为自己 { temp->next[i]->fail = root; } else { p = temp->fail; //将父节点的fail传给儿子 while(p != NULL) { if(p->next[i] != NULL) { temp->next[i]->fail = p->next[i]; break; } p = p->fail; } if(p == NULL) temp->next[i]->fail = root;//如果失败，fail就为根节点 } q[tail++] = temp->next[i]; } } }}void ac_automation(char ch[]){ node *p = root; int len = strlen(ch); for(int i = 0; i < len; i++) //主文本搜索到哪了 { int x = ch[i] - 'a'; while(p->next[x] == NULL&& p != root) p = p->fail; //如果失败就从fail开始再找 p = p->next[x]; if(p == NULL) p = root; //判断是否找到了 node *temp = p; while(temp != root) { if(temp->sum >= 0) //如果没加过，就加 { cnt += temp->sum; temp->sum = -1; } else break; //加过就不加了 temp = temp->fail; //把相同后缀的单词都加上 } }}int main(){ int T; scanf("%d",&T); while(T--) { root=new node; for(int j=0;j<26;j++) root->next[j] = NULL; root->fail = 0; root->sum = 0; scanf("%d",&N); getchar(); for(int i = 1; i <= N; i++) { gets(key); Insert(key); } gets(pattern); cnt = 0; build_fail_pointer(); ac_automation(pattern); printf("%d\n",cnt); } return 0;}
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<queue> using namespace std; #define duke(i,a,n) for(int i = a;i <= n;i++) #define lv(i,a,n) for(int i = a;i >= n;i--) #define clean(a) memset(a,0,sizeof(a)) const int INF = 1 << 30; const int mod = 998244353; typedef double db; template <class T> void read(T &x) { char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') {x = x * 10 + c - '0';if(x > mod) x %= mod;} if(op) x = -x; } template <class T> void write(T x) { if(x < 0) putchar('-'), x = -x; if(x >= 10) write(x / 10); putchar('0' + x % 10); } const int maxn = 1e6 + 5; char s[maxn]; int ch[maxn][30],cnt = 0,val[maxn],f[maxn],n; int getnum(char c) { return c - 'a'; } void insert(char *s) { int m = strlen(s); int now = 0; duke(i,0,m - 1) { int c = getnum(s[i]); if(!ch[now][c]) ch[now][c] = ++cnt; now = ch[now][c]; } val[now]++; } void build() { queue <int> q; duke(i,0,25) { if(ch[0][i]) q.push(ch[0][i]); } while(!q.empty()) { int now = q.front(); q.pop(); duke(i,0,25) { if(ch[now][i]) f[ch[now][i]] = ch[f[now]][i],q.push(ch[now][i]); else ch[now][i] = ch[f[now]][i]; } } } int query(char *s) { int len = strlen(s),now = 0,ans = 0; duke(i,0,len - 1) { int c = getnum(s[i]); now = ch[now][c]; for(int j = now;j && val[j] != -1;j = f[j]) ans += val[j],val[j] = -1; } return ans; } int main() { read(n); duke(i,1,n) { scanf("%s",s); insert(s); } build(); scanf("%s",s); printf("%d\n",query(s)); return 0; }
转载于:https://www.cnblogs.com/DukeLv/p/8406309.html
相关资源：数据结构—成绩单生成器