前言
<——来都来了,就点个赞呗~
感觉y总讲的比算法基础课时讲的好多了
AC 自动机一共分3部分
1. insert: 插入字符串,和Trie的插入方式一样
2. build: 构建 AC 自动机,预处理 fail 指针,就相当于 KMP 中的预处理 next 数组
3. query: 查询函数,和 KMP 中的匹配部分类似
暴力做法
思路
build 和 query 中失配后就暴力跳 fail
query 中由于有多个模式串,所以要把所有 fail 都跳一遍
时间复杂度最坏为 $O(n^2)$
但是由于数据太弱,所以可以AC
Code
#include<bits/stdc++.h>
#define son(x,y) AC[x].son[y]
#define fail(x) AC[x].fail
#define cnt(x) AC[x].cnt
using namespace std;
int tot,T,n,m;
string str;
struct node
{
int son[26];
int fail;
int cnt;
}AC[500000];
void insert(string s)
{
int rt=0;
for (int i:s)
{
i-='a';
if (!son(rt,i)) son(rt,i)=(++tot);
rt=son(rt,i);
}
cnt(rt)++;
}
void build()
{
queue<int> q;
for (int i=0;i<26;i++)
if (son(0,i))
q.push(son(0,i));
while (!q.empty())
{
int u=q.front();
q.pop();
for (int i=0;i<26;i++)
{
int v=son(u,i);
if (!v) continue;
int j=fail(u);
while (j&&!son(j,i)) j=fail(j);
if (son(j,i)) j=son(j,i);
fail(v)=j;
q.push(v);
}
}
}
int query(string s)
{
int ans=0;
for (int i=0,j=0;i<s.size();i++)
{
int t=s[i]-'a';
while (j&&!son(j,t)) j=fail(j);
if (son(j,t)) j=son(j,t);
int p=j;
while (p&&~cnt(p))
{
ans+=cnt(p);
cnt(p)=-1;
p=fail(p);
}
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>T;
while (T--)
{
cin>>n;
while (n--) {
cin>>str;
insert(str);
}
build();
cin>>str;
cout<<query(str)<<endl;
memset(AC,0,sizeof AC);
}
return 0;
}
Trie 图优化
思路
由于每次都暴力跳 fail,所以太慢了
这里可以用一种类似并查集的路径压缩的方法,失配后 fail 就直接指向最后的匹配成功的位置
- build 函数中,本来如果没有当前子节点就 continue,但是这里就直接父节点的 fail 指向的节点的子节点
- 如果有当前节点,由于之前的 fail 指针都是正确的,所以可以直接把 fail 指向父节点的 fail 指向的子节点
- query 函数中,直接把 j 变成自己的子节点
Code
#include<bits/stdc++.h>
#define son(x,y) AC[x].son[y]
#define fail(x) AC[x].fail
#define cnt(x) AC[x].cnt
using namespace std;
int tot,T,n,m;
string str;
struct node
{
int son[26];
int fail;
int cnt;
}AC[500000];
void insert(string s)
{
int rt=0;
for (int i:s)
{
i-='a';
if (!son(rt,i)) son(rt,i)=(++tot);
rt=son(rt,i);
}
cnt(rt)++;
}
void build()
{
queue<int> q;
for (int i=0;i<26;i++)
if (son(0,i))
q.push(son(0,i));
while (!q.empty())
{
int u=q.front();
q.pop();
for (int i=0;i<26;i++)
{
int v=son(u,i);
if (v) {
fail(v)=son(fail(u),i);
q.push(v);
}
else
son(u,i)=son(fail(u),i);
}
}
}
int query(string s)
{
int ans=0;
for (int i=0,j=0;i<s.size();i++)
{
int t=s[i]-'a';
j=son(j,t);
int p=j;
while (p&&~cnt(p))
{
ans+=cnt(p);
cnt(p)=-1;
p=fail(p);
}
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>T;
while (T--)
{
cin>>n;
while (n--) {
cin>>str;
insert(str);
}
build();
cin>>str;
cout<<query(str)<<endl;
memset(AC,0,sizeof AC);
}
return 0;
}