我：“woc。。。AC自动机？”
我：“可以自动AC？？？”
然鹅。。。
大佬：“傻。。。”
我：“(⊙_⊙)?”
大佬：“缺。。。”
我：“。。。。。。”
（大佬。。。卒 | 逃。。。）
emm。。。好吧。。。让我们来看看AC自动机是啥。。。
写在前面：如果没有学过 KMP 和 Trie树，请先理解这两个算法。。。
这个东西因为是一个歪果仁发明，然后两个单词的首字母为AC，所以就被叫做AC自动机了。。。
这个东西简单来说 AC自动机 == Trie + KMP
我们需要维护的东西也很简单，类似于Trie树上的KMP中的next数组。。。（作用类似，代表意义不同）
在AC自动机中有一个 fail 叫做失配指针。。。就是用它来进行跳转进行匹配
这样我们就可以发现。。。
Trie树维护多个字符串的功能 + KMP判子串的功能 == AC自动机匹配多个字符串
emm。。。讲解原理比较麻烦，直接看代码和注释比较好懂，当然建议根据大体的原理先瞎搞一波再看
呆码：
#include#include #include #include using namespace std;struct asd{ int fail; // 失配指针 int vis[26]; // 子节点的位置 int end; // 标记有几个单词以这个节点结尾 } AC[1000010];int rt,cnt,l,n;char ch[1000010];inline void build(char *ch){ int l=strlen(ch+1); int now=rt,v; for(int i=1;i<=l;i++) { v=ch[i]-'a'; if(!AC[now].vis[v]) AC[now].vis[v]=++cnt; now=AC[now].vis[v]; } AC[now].end+=1;}inline void get_fail(){ queue Q; for(int i=0;i<=25;i++) // 第一层肯定没有之前的点与他匹配 if(AC[rt].vis[i]) Q.push(AC[rt].vis[i]); // 因为默认是 0 所以没有写指向根节点 while(!Q.empty()) { int u=Q.front(); Q.pop(); for(int i=0;i<=25;i++) // 枚举所有子节点 { if(AC[u].vis[i]) // 存在这个子节点 { AC[AC[u].vis[i]].fail=AC[AC[u].fail].vis[i]; // 子节点的fail指针指向当前节点的 // fail指针所指向的节点的相同子节点 Q.push(AC[u].vis[i]); } else //不存在这个子节点 AC[u].vis[i]=AC[AC[u].fail].vis[i]; // 当前节点的这个子节点指向当 // 前节点fail指针的这个子节点 } }}inline int query(char *ch){ int l=strlen(ch+1); int now=rt,ans=0,u; for(int i=1;i<=l;i++) { u=ch[i]-'a'; now=AC[now].vis[u]; for(int j=now; j && AC[j].end!=-1; j=AC[j].fail) { ans+=AC[j].end; AC[j].end=-1; } } return ans;}int main(){ cin>>n; for(int i=1;i<=n;i++) { scanf("%s",ch+1); build(ch); } get_fail(); scanf("%s",ch+1); printf("%d\n",query(ch)); return 0;}