题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=2222

题意：给你一系列子串，再给你一个主串问你主串一共有几个匹配子串

原来使用字典树写的但数据有点大TLE了，然后就开始学习ac自动机了，ac自动机就像是多串匹配的kmp原理也是类似的。

这题可以练一下手写ac自动机模版。

#include <iostream>#include <cstring>#include <cstdio>#include <queue>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<int>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;}

hdu 2222 Keywords Search（ac自动机）