题目链接
题意：给你一系列子串，再给你一个主串问你主串一共有几个匹配子串
原来使用字典树写的但数据有点大TLE了，然后就开始学习ac自动机了，ac自动机就像是多串匹配的kmp原理也是类似的。
这题可以练一下手写ac自动机模版。
#include#include #include #include using namespace std;const int M = 5e5 + 50;int Next[M][26] , fail[M] , End[M] , root , L , cnt;char str[60] , sl[M * 2];int newnode() { for(int i = 0 ; i < 26 ; i++) { Next[L][i] = -1; } End[L++] = 0; return L - 1;}void init() { L = 0; root = newnode();}void build(char s[]) { int len = strlen(s); int now = root; for(int i = 0 ; i < len ; i++) { int id = s[i] - 'a'; if(Next[now][id] == -1) { Next[now][id] = newnode(); } now = Next[now][id]; } ++End[now];}void get_fail() { queue q; fail[root] = root; for(int i = 0 ; i < 26 ; 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 < 26 ; 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]); } } }}void match(char s[]) { int now = root; int len = strlen(s); for(int i = 0 ; i < len ; i++) { int id = s[i] - 'a'; now = Next[now][id]; int temp = now; while(temp != root) { cnt += End[temp]; End[temp] = 0; temp = fail[temp]; } }}int main(){ int t; scanf("%d" , &t); while(t--) { int n; scanf("%d" , &n); init(); for(int i = 0 ; i < n ; i++) { scanf("%s" , str); build(str); } get_fail(); scanf("%s" , sl); cnt = 0; match(sl); printf("%d\n" , cnt); } return 0;}