【题目链接】
https://www.luogu.org/problem/P3808
【题意】
给定n个模式串和1个文本串，求有多少个模式串在文本串里出现过。
【题解】
不再介绍基础知识了，就是裸的模板题，直接贴上来。
【代码】
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 5e5+;
const int M = 1e6+;
queue < int > Q ;
typedef struct Aho_Corasick_Automaton{
int Son[N][],End[N],Fail[N],idx;
void Init(){
idx = ;
while( !Q.empty() ) Q.pop() ;
memset(Son , , sizeof Son );
memset(End , , sizeof End );
memset(Fail, , sizeof Fail );
}
void Insert(char s[]){
int p = ;
for(int i=;s[i];i++){
int t = s[i] - 'a';
if( !Son[p][t] )
Son[p][t] = ++idx;
p = Son[p][t] ;
}
End[p] ++ ;
} void Build(){
for(int i=;i<;i++){
if( Son[][i] )
Fail[Son[][i]] = ,Q.push(Son[][i]);
} while( !Q.empty() ){
int u = Q.front() ;
Q.pop(); for(int i=;i<;i++){
if( Son[u][i] ){
Fail[Son[u][i]] = Son[Fail[u]][i] ;
Q.push( Son[u][i] );
}else{
Son[u][i] = Son[Fail[u]][i];
}
}
}
} void Query(char s[]){
int p = ,res = ;
for(int i=;s[i];i++){
int t = s[i] - 'a';
p = Son[p][t] ;
for(int j=p ; j && ~End[j] ; j = Fail[j] ){
res += End[j] ;
End[j] = - ;
}
}
printf("%d\n",res);
}
}AC_Machine ;
AC_Machine AC ;
char s[M];
int n;
int main(){ scanf("%d",&n);
//AC.Init(); for(int i=;i<n;i++){
scanf("%s",s);
AC.Insert(s);
}
AC.Build();
scanf("%s",s);
AC.Query(s);
return ;
}
AC自动机1
【题目链接】
https://www.luogu.org/problem/P3796
【题意】
有N个由小写字母组成的模式串以及一个文本串T。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串T中出现的次数最多。
和模板题1一样，就是最后结尾的标记加上一些小改动。
【代码】
// luogu-judger-enable-o2
#pragma GCC optimize(2) #include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 5e5+1e4;
const int M = 1e6+;
char Str[][],s[M];
int Cnt[N],vis[N],n;
queue < int > Q ;
typedef struct Aho_Corasick_Automaton{
int Son[N][],End[N],Fail[N],idx;
void Init(){
idx = ;
while( !Q.empty() ) Q.pop() ;
memset(Cnt , , sizeof Cnt );
memset(vis , , sizeof vis );
memset(Son , , sizeof Son );
memset(End , , sizeof End );
memset(Fail, , sizeof Fail );
}
void Insert(char s[],int Id ){
int p = ;
for(int i=;s[i];i++){
int t = s[i] - 'a';
if( !Son[p][t] )
Son[p][t] = ++idx;
p = Son[p][t] ;
}
End[p] ++ ;
vis[p] = Id;
} void Build(){
for(int i=;i<;i++){
if( Son[][i] )
Fail[Son[][i]] = ,Q.push(Son[][i]);
} while( !Q.empty() ){
int u = Q.front() ;
Q.pop(); for(int i=;i<;i++){
if( Son[u][i] ){
Fail[Son[u][i]] = Son[Fail[u]][i] ;
Q.push( Son[u][i] );
}else{
Son[u][i] = Son[Fail[u]][i];
}
}
}
} void Query(char s[]){
int p = ,res = ;
for(int i=;s[i];i++){
int t = s[i] - 'a';
p = Son[p][t] ;
for(int j=p ; j ; j = Fail[j] ){
if( End[j] ){
Cnt[vis[j]] ++ ;
}
}
}
for(int i=;i<n;i++){
res = max( Cnt[i] , res ) ;
}
cout << res << endl;
//printf("%d\n",res);
for(int i=;i<n;i++){
if( res == Cnt[i] ){
cout << Str[i] << endl;
}
}
}
}AC_Machine ;
AC_Machine AC ; int main(){ ios_base :: sync_with_stdio(false);
cin.tie(NULL) , cout.tie(NULL); while ( cin >> n ,n ){
AC.Init();
for(int i=;i<n;i++){
//scanf("%s",s);
cin >> Str[i];
AC.Insert(Str[i],i);
}
AC.Build();
//scanf("%s",s);
cin >> s ;
AC.Query(s);
}
return ;
}
AC自动机2
【题目链接】
https://www.luogu.org/problem/P5357
【题意】
给你一个文本串 SS 和 nn 个模式串 T_{1..n}，请你分别求出每个模式串 Ti 在 S 中出现的次数。
【题解】
这个题目就非常有意思了，
其实我还没怎么想就去洛谷看题解了，
发现是还是各显神通呀。大家都很厉害，我这里提供三个人的做法。
其实道理都是一样的。
一种是：进行类似于差分累加的过程。
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 2e5+;
const int M = 2e6+;
typedef struct node{
int son[],fail;
int& operator [] (int x) {return son[x];}
}Node; Node Trie[N]; int Q[N],head[N],Next[N],Ans[N],d[N];
int Head,Tail,n,idx;
char s[M]; void Insert(char s[],int Id ){
int p = ;
for(int i=;s[i];i++){
int t = s[i] - 'a';
if( !Trie[p][t] )
Trie[p][t] = ++idx;
p = Trie[p][t] ;
}
Next[Id] = head[p] ;
head[p] = Id;
} void Build(){
Head = , Tail = ;
for(int i=;i<;i++) if( Trie[][i] ) Q[++Tail] = Trie[][i];
while( Head <= Tail ){
int u = Q[Head++] ;
for(int i=;i<;i++){
if( Trie[u][i] ){
Trie[Trie[u][i]].fail = Trie[Trie[u].fail][i] ;
Q[++Tail] = Trie[u][i] ;
}else{
Trie[u][i] = Trie[Trie[u].fail][i];
}
}
}
} void Query(char s[]){
int p = ,res = ;
for(int i=;s[i];i++){
int t = s[i] - 'a';
p = Trie[p][t] ;
d[p] ++ ;
}
for(int i=idx;i;i--){
for(int j=head[Q[i]] ; j ; j = Next[j] ) Ans[j] = d[Q[i]];
d[ Trie[Q[i]].fail ] += d[ Q[i] ];
}
for(int i=;i<=n;i++){
cout << Ans[i] << endl ;
}
} int main(){ ios_base :: sync_with_stdio(false);
cin.tie(NULL) , cout.tie(NULL); cin >> n;
for(int i=;i<=n;i++){
cin >> s;
Insert(s,i);
}
Build();
cin >> s ;
Query(s);
return ;
}
AC自动机3—差分做法
一种是拓扑排序的做法
#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+;
typedef struct Node {
int son[],Fail,End,Cnt;
void Clear(){
memset(son,,sizeof son );
Fail = End = Cnt = ;
}
int & operator [] (int x){ return son[x];}
}Node ;
Node Trie[N];
char s[N];
int Ans,idx=,n,Head,Tail;
int Mp[N],vis[N],Ind[N],Q[N]; void Insert( char s[] , int Id ){
int p = ;
for(int i=;s[i];i++){
int t = s[i] - 'a';
if( !Trie[p][t] )
Trie[p][t] = ++idx ;
p = Trie[p][t] ;
}
if( !Trie[p].End ) Trie[p].End = Id;
Mp[Id] = Trie[p].End
;
} void Build(){
Head = , Tail = ;
for(int i=;i<;i++){ Trie[][i] = ; }
Q[++Tail] = ;
while( Head <= Tail ){
int u = Q[Head++] ;
for(int i=;i<;i++){
int To = Trie[u][i] ;
if( To ){
Trie[To].Fail = Trie[Trie[u].Fail][i];
Ind[ Trie[To].Fail ] ++ ;
Q[++Tail] = Trie[u][i];
}else{
Trie[u][i] = Trie[Trie[u].Fail][i];
}
}
}
}
void Topu( ){
Head = , Tail = ;
for(int i=;i<=idx;i++) if( !Ind[i] ) Q[++Tail] = i; while( Head <= Tail ){
int u = Q[Head++];
vis[ Trie[u].End ] = Trie[u].Cnt ;
int To = Trie[u].Fail ;
Ind[To] -- ;
Trie[To].Cnt += Trie[u].Cnt;
if( Ind[To] == )
Q[++Tail] = To ;
}
}
void Query(char s[]){
int p = ;
for(int i=;s[i];i++){
p = Trie[p][s[i]-'a'];
Trie[p].Cnt ++ ;
}
} int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%s",s);
Insert( s, i );
}
Build() ;
scanf("%s",s);
Query(s);
Topu();
for(int i=;i<=n;i++){
printf("%d\n",vis[Mp[i]]);
}
} /* 5
a
bb
aa
abaa
abaaa
abaaabaa 6
0
3
2
1 */
AC自动机3—拓扑排序
最后一种是最正宗的做法了，建fail树。
#include<bits/stdc++.h>
using namespace std; const int N = 2e6+;
void dfs(int u);
void Add_edge(int u,int v); char s[N];
int head[N],nxt[N],to[N], cnt ; int n,idx=;
int Trie[N][],fail[N],Match[N],Sz[N]; int Q[N],Head,Tail; void Insert(char s[] ,int Id){
int p = ;
for(int i=;s[i];i++){
int t = s[i]-'a';
if( !Trie[p][t] ){
Trie[p][t] = ++idx;
}
p = Trie[p][t] ;
}
Match[Id] = p ;
}
void Build(){
Head = , Tail = ;
for(int i=;i<;i++)
Trie[][i] = ;
Q[++Tail] = ;
while( Head <= Tail ){
int u = Q[Head++] ;
for(int i=;i<;i++){
if( Trie[u][i] ){
fail[Trie[u][i]] = Trie[fail[u]][i];
Q[++Tail] = Trie[u][i];
}else{
Trie[u][i] = Trie[fail[u]][i];
}
}
}
}
void Query(char s[]){
for(int p=,i=;s[i];i++){
p = Trie[p][s[i]-'a'];
Sz[p] ++ ;
}
for(int i=;i<=idx;i++){
Add_edge( fail[i] , i );
}
dfs( );
for(int i=;i<=n;i++){
printf("%d\n",Sz[Match[i]]);
}
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%s",s);
Insert(s,i);
}
Build();
scanf("%s",s);
Query(s);
return ;
}
void dfs(int u){
for(int i=head[u];i;i=nxt[i]){
int v = to[i] ;
dfs(v);
Sz[u] += Sz[v];
}
}
void Add_edge(int u,int v){
nxt[++cnt]= head[u];
head[u] = cnt ;
to[cnt] = v ;
} /* 5
a
bb
aa
abaa
abaaa
abaaabaa 6
0
3
2
1 */
AC自动机3—fail树