点击打开链接
在一个字符串中出现模板串的个数
#include <iostream> #include <string.h> #include <stdio.h> #include <algorithm> #include <queue> #include <math.h> #define MOD 1000000007 using namespace std; const int N = 1e6+10; const int M = 26; struct Trie{ int next[N][M],end[N],fail[N]; int root,L; int newNode(){ for(int i = 0; i < M; ++i){ next[L][i] = -1; } end[L++] = 0; return L-1; } void init(){ L = 0; root = newNode(); } void insert(char buf[]){ int now = root; for(int i = 0; buf[i]; ++i){ int x = buf[i]-'a'; if(next[now][x] == -1) next[now][x] = newNode(); now = next[now][x]; } end[now]++; } void build(){ queue<int>Q; fail[root] = root; for(int i = 0; i < M; ++i){ 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(int i = 0; i < M; ++i){ 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 now = root; int res = 0; for(int i = 0; buf[i]; ++i){ now = next[now][buf[i]-'a']; int temp = now; while(temp != root){ res += end[temp]; end[temp] = 0; temp = fail[temp]; } } return res; } }; char buf[N]; Trie ac; int main() { int T; int n; scanf("%d",&T); while(T--){ scanf("%d",&n); ac.init(); for(int i = 0; i < n; ++i){ scanf("%s",buf); ac.insert(buf); } ac.build(); scanf("%s",buf); printf("%d\n",ac.query(buf)); } return 0; }