学习笔记::AC自动机
生活随笔
收集整理的這篇文章主要介紹了
学习笔记::AC自动机
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
最先開始以為和自動刷題機是一個東西。。。
其實就是kmp的一個拓展。學完kmp再學這個就會發現其實不難
1.kmp是一個串匹配一個串，但是當我們想用多個串匹配一個文本的時候，kmp就不行了，因此我們有了AC自動機
2.很明顯我們用單詞去匹配文本是肯定要一個一個枚舉單詞去匹配的，那么我們換個思路，用文本去匹配串。
3.AC自動機的原理：我不是很懂，口胡一下：
1.建立一顆trie，讀入單詞后把單詞一個一個插入到trie
3.進行文本匹配。把文本放到AC自動機上。想象一下：把AC自動機的root看成一個入口，把串的開頭放進去，串一個一個字符地跑進自動機里，每個字符都對應上了一個節點。（要不為什么叫自動機）
#include<bits/stdc++.h>
using namespace std;
#define N 1000010
struct trie
{
int ch[],fail,val,vis;
}t[N>>];
int n,root,ans,cnt;
char s[N];
int q[N];
void ins(char s[])
{
int now=root,len=strlen(s+);
for(int i=;i<=len;i++)
{
int x=s[i]-'a';
if(!t[now].ch[x]) t[now].ch[x]=++cnt;
now=t[now].ch[x];
}
t[now].val++;
}
void construct_AC()
{
int l=,r=;
q[++r]=root;
while(l<=r)
{
int u=q[l++];
for(int i=;i<;i++)
{
int v=t[u].ch[i]; if(!v) continue;
if(u==root) t[v].fail=root;
else
{
int now=t[u].fail;
while(now!=root&&!t[now].ch[i]) now=t[now].fail;
if(t[now].ch[i]) now=t[now].ch[i];
t[v].fail=now;
}
q[++r]=v;
}
}
}
void AC(char s[])
{
int len=strlen(s+),now=root;
for(int i=;i<=len;i++)
{
int u=s[i]-'a';
while(now!=root&&!t[now].ch[u]) now=t[now].fail;
if(t[now].ch[u])
{
now=t[now].ch[u];
for(int pos=now;pos!=root&&!t[pos].vis;pos=t[pos].fail)
{
ans+=t[pos].val; t[pos].vis=;
}
}
}
}
int main()
{
int T; scanf("%d",&T);
while(T--)
{
memset(t,,sizeof(t)); ans=; cnt=;
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%s",s+);
ins(s);
}
construct_AC();
scanf("%s",s+);
AC(s);
printf("%d\n",ans);
}
return ;
}
總結
以上是生活随笔為你收集整理的学习笔记::AC自动机的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： InnoDB Undo Log
- 下一篇： 什么是非全尺寸备胎?（非全尺寸备胎是什么