【模版】AC自动机（简单版）

题目背景

这是一道简单的AC自动机模版题。

用于检测正确性以及算法常数。

为了防止卡OJ，在保证正确的基础上只有两组数据，请不要恶意提交。

题目描述

给定n个模式串和1个文本串，求有多少个模式串在文本串里出现过。

输入输出格式

输入格式：

第一行一个n，表示模式串个数；

下面n行每行一个模式串；

下面一行一个文本串。

输出格式：

一个数表示答案

输入输出样例

输入样例#1：

2

a

aa

aa

输出样例#1：

说明

subtask1[50pts]:∑length(模式串)<=10^6,length(文本串)<=10^6,n=1；

subtask2[50pts]:∑length(模式串)<=10^6,length(文本串)<=10^6；

洛谷的一道AC自动机的模板题，正好整理一下模板，看了看wsj的代码并且结合最近几天所听到的一些知识，整理了整理也就大了一下，然后就过了，发现并没有多大难度，

只要理会就好了，之后我会再写一篇关于AC自动机的Blog，现在先水水几道水题，模板题先过了，再说。

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 #include<iostream>

 #include<cstring>

 #include<queue>

 using namespace std;

 int n,cnt=;

 char s[];

 struct Node

 {

     int c[],suf,flag;

 }tree[];

 inline void Ins()

 {

     int head=,l=strlen(s);

     for (int i=;i<l;i++)

     {

         int now=s[i]-'a';

         if (!tree[head].c[now]) tree[head].c[now]=++cnt;

         head=tree[head].c[now];

     }

     tree[head].flag++;

 }

 void Make_AC()

 {

     for (int i=;i<;i++) tree[].c[i]=;

     int head=,tail=;

     queue<int>q;

     while (!q.empty()) q.pop();

     tree[].suf=;

     q.push();

     while (!q.empty())

     {

         int u=q.front();

         q.pop();

         for (int i=;i<;i++)

             if (tree[u].c[i])

             {

                 tree[tree[u].c[i]].suf=tree[tree[u].suf].c[i];

                 q.push(tree[u].c[i]);

             }

             else tree[u].c[i]=tree[tree[u].suf].c[i];

     }

 }

 void Solve()

 {

     scanf("%s",s);

     int ans=,head=,len=strlen(s);

     for (int i=;i<len;i++)

     {

         int now=s[i]-'a';

         head=tree[head].c[now];

         for (int j=head;j&&tree[j].flag!=-;j=tree[j].suf)

             ans+=tree[j].flag,tree[j].flag=-;

     }

     printf("%d\n",ans);

 }

 int main()

 {

     scanf("%d",&n);

     while (n--){scanf("%s",s);Ins();}

     Make_AC();

     Solve();

 }

巴特西

【模版】AC自动机（简单版）

题目背景

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章