2021.09.01 自动机

AC自动机

学习记录：

void build(){
	for(int i=0;i<26;i++)if(tr[0][i])q.push(tr[0][i]);
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=0;i<26;i++)
		if(tr[x][i])
		fail[tr[x][i]]=tr[fail[x]][i],q.push(tr[x][i]);
		else tr[x][i]=tr[fail[x]][i];
		//通过else来简化一直转跳
		//相当于又给不存在的点和已经存在的序列一样的点合并 
	}
}
int query(char *t){
	int u=0,ans=0;
	for(int i=1;t[i];i++){
		u=tr[u][t[i]-'a'];
		for(int j=u;j&&e[j]!=-1;j=fail[j])res+=e[j],e[j]=-1;
	}
	return res;
} 

重点：

1.fail的意义！

模板：

P3808 【模板】AC自动机（简单版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;

const int N=1e6+10;

namespace ac{
	int tr[N][30],tot,e[N],fail[N];
	//fail数组是当前状态有相同状态的最长前缀 
	void insert(char *s){
		int u=0;
		for(int i=1;s[i];i++){
			if(!tr[u][s[i]-'a'])tr[u][s[i]-'a']=++tot;
			u=tr[u][s[i]-'a'];
		}
		++e[u];
	}
	queue<int>q;
	void build(){
		for(int i=0;i<26;i++)if(tr[0][i])q.push(tr[0][i]);
		while(!q.empty()){
			int u=q.front();q.pop();
			for(int i=0;i<26;i++){
				if(tr[u][i])
				fail[tr[u][i]]=tr[fail[u]][i],q.push(tr[u][i]);
				else tr[u][i]=tr[fail[u]][i];
			}
		}
	}
	int query(char *t){
		int u=0,ans=0;
		for(int i=1;t[i];i++){
			u=tr[u][t[i]-'a'];
			for(int j=u;j&&e[j]!=-1;j=fail[j])
			ans+=e[j],e[j]=-1; 
		}
		return ans;
	}
}

int n;
char s[N];

inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*w;
}

int main(){
	n=read();
	for(int i=1;i<=n;i++)scanf("%s",s+1),ac::insert(s);
	scanf("%s",s+1);
	ac::build();
	cout<<ac::query(s);
	return 0;
}

P3796 【模板】AC自动机（加强版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

while (~scanf("%d%d",&n,&m))_笃行999-CSDN博客

while(scanf("%d",&n)!=EOF) 用法_笃行999-CSDN博客

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;

const int N=16000;

namespace ac{
	int tr[N][30],tot,id[N],fail[N],val[N],cnt[200];
	//fail数组是当前状态有相同状态的最长前缀 
	void init(){
		tot=0;
		memset(fail,0,sizeof(fail));
		memset(tr,0,sizeof(tr));
		memset(val,0,sizeof(val));
		memset(id,0,sizeof(id));
		memset(cnt,0,sizeof(cnt));
	}
	void insert(char *s,int idi){
		int u=0;
		for(int i=1;s[i];i++){
			if(!tr[u][s[i]-'a'])tr[u][s[i]-'a']=++tot;
			u=tr[u][s[i]-'a'];
		}
		id[u]=idi;
	}
	queue<int>q;
	void build(){
		for(int i=0;i<26;i++)if(tr[0][i])q.push(tr[0][i]);
		while(!q.empty()){
			int u=q.front();q.pop();
			for(int i=0;i<26;i++){
				if(tr[u][i])
				fail[tr[u][i]]=tr[fail[u]][i],q.push(tr[u][i]);
				else tr[u][i]=tr[fail[u]][i];
			}
		}
	}
	int query(char *t){
		int u=0,ans=0;
		for(int i=1;t[i];i++){
			u=tr[u][t[i]-'a'];
			for(int j=u;j;j=fail[j])++val[j];
		}
		for(int i=0;i<=tot;i++)
		if(id[i])ans=max(ans,val[i]),cnt[id[i]]=val[i];
		return ans;
	}
}

const int M=1e6+10;
int n;
char s[200][100],t[M];

inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*w;
}

int main(){
	while((n=read())&&n){
		ac::init();
		for(int i=1;i<=n;i++)scanf("%s",s[i]+1),ac::insert(s[i],i);
		ac::build();
		scanf("%s",t+1);
		int x=ac::query(t);
		cout<<x<<endl;
		for(int i=1;i<=n;i++)if(ac::cnt[i]==x)printf("%s\n",s[i]+1);
	}
	return 0;
}

P5357 【模板】AC自动机（二次加强版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

重点：

1.strlen对于char * 无用，只能得出来0

shift！地址有个锤子的长度？！

2021.11.09 补充：有用，从0开始strlen(S)，从1开始strlen(S+1)。

[C++ 学习——char * ,char a ],char ** ,char *a[] 的区别_xiaohu的博客-CSDN博客

string、char、char*之间的转换

https://www.cnblogs.com/Pillar/p/4206452.html

2.memset对于struct有可能报错

3.AC自动机的优化形式

题解 P5357 【【模板】AC自动机（二次加强版）】 - hyfhaha 的博客 - 洛谷博客 (luogu.com.cn)

满分代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue> 
#include<cstring>
using namespace std;

const int N=2e6+10;
int n,tot,cnt[200010],ans,ru[N],fa[N];
char s[N],t[N];
struct node{
	int son[26],fail,flag,ans;
	void clear(){
		memset(son,0,sizeof(son));
		flag=fail=ans=0;
	}
}trie[N];
queue<int>q;

inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*w;
}
void insert(char *s,int idi){
	int u=0,len=strlen(s);
	//cout<<len<<endl;//
	for(int i=1;s[i];i++){
		if(trie[u].son[s[i]-'a']==0)trie[u].son[s[i]-'a']=++tot;//,
		//cout<<"u "<<u<<" s[i]-'a' "<<s[i]-'a'<<" tot "<<tot<<endl;
		u=trie[u].son[s[i]-'a'];
		//cout<<u<<" ";
	}
	if(!trie[u].flag)trie[u].flag=idi;
	fa[idi]=trie[u].flag;
	//cout<<endl;
	//cout<<idi<<" fa "<<fa[idi]<<" flag "<<trie[u].flag<<" u "<<u<<endl;
}
void build(){
	for(int i=0;i<26;i++)if(trie[0].son[i])q.push(trie[0].son[i]);
	while(!q.empty()){
		int x=q.front();q.pop();
		int faili=trie[x].fail;
		for(int i=0;i<26;i++){
			if(trie[x].son[i])
			trie[trie[x].son[i]].fail=trie[trie[x].fail].son[i],
			q.push((trie[x].son[i])),
			++ru[trie[trie[x].son[i]].fail];
			else trie[x].son[i]=trie[trie[x].fail].son[i];
		}
	}
}
void topu(){
	for(int i=0;i<=tot;i++)if(!ru[i])q.push(i);
	while(!q.empty()){
		int x=q.front();q.pop();
		cnt[trie[x].flag]=trie[x].ans;
		int faili=trie[x].fail;
		--ru[faili];
		trie[faili].ans+=trie[x].ans;
		if(!ru[faili])q.push(faili);
	}
}
void query(char *t){
	int u=0,len=strlen(t);
	for(int i=1;t[i];i++)
	u=trie[u].son[t[i]-'a'],++trie[u].ans;
}

int main(){
	//memset(&trie,0,sizeof(trie));
	n=read();
	for(int i=1;i<=n;i++)scanf("%s",s+1),insert(s,i);
	build();
	//for(int i=1;i<=n;i++)cout<<fa[i]<<" ";cout<<endl<<endl;
	scanf("%s",t+1);
	query(t);
	topu();
	for(int i=1;i<=n;i++)printf("%d\n",cnt[fa[i]]);
	return 0;
}

76分代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<map>
using namespace std;

const int N=2e5+10;
int n,top;

namespace ac{
	int tr[N][30],tot,id[N],fail[N],val[N],cnt[N],fa[N];
	//fail数组是当前状态有相同状态的最长前缀 
	void init(){
		tot=0;
		memset(fail,0,sizeof(fail));
		memset(tr,0,sizeof(tr));
		memset(val,0,sizeof(val));
		memset(id,0,sizeof(id));
		memset(cnt,0,sizeof(cnt));
		//for(int i=1;i<=)
	}
	void insert(char *s,int idi){
		int u=0;
		for(int i=1;s[i];i++){
			if(!tr[u][s[i]-'a'])tr[u][s[i]-'a']=++tot;
			u=tr[u][s[i]-'a'];
		}
		if(id[u])fa[idi]=id[u];
		else id[u]=idi;
	}
	queue<int>q;
	void build(){
		for(int i=0;i<26;i++)if(tr[0][i])q.push(tr[0][i]);
		while(!q.empty()){
			int u=q.front();q.pop();
			for(int i=0;i<26;i++){
				if(tr[u][i])
				fail[tr[u][i]]=tr[fail[u]][i],q.push(tr[u][i]);
				else tr[u][i]=tr[fail[u]][i];
			}
		}
	}
	void query(char *t){
		int u=0,ans=0;
		for(int i=1;t[i];i++){
			u=tr[u][t[i]-'a'];
			for(int j=u;j;j=fail[j])++val[j];
		}
		for(int i=0;i<=tot;i++)
		if(id[i])cnt[id[i]]=val[i];
		//return ans;
		for(int i=1;i<=n;i++){
			if(!fa[i])cout<<cnt[i]<<endl;
			else cout<<cnt[fa[i]]<<endl;
		}
	}
}

const int M=1e6+10;
char s[M],t[M*2];
map<string,int>mapi;

inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*w;
}

int main(){
	n=read();
	//for(int i=1;i<=n;i++)ac::fa[i]=i;
	for(int i=1;i<=n;i++){
		ac::fa[i]=i;
		scanf("%s",s+1);
		ac::insert(s,i);
	}
	//for(int i=1;i<=n;i++)cout<<ac::fa[i]<<" ";
	ac::build();
	scanf("%s",t+1);
	ac::query(t);
	return 0;
}

fail树

[P2414 NOI2011] 阿狸的打字机 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

别人代码：

#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
const int MaxN = 1e5 + 10;

struct Trie {
    int Vis[30], End, Fail, Fa;
}Ac[MaxN];
int P = 1;

struct Edge {
    int To, Next;
}Road[MaxN];

struct Query {
    int X, Y;
};
int Last[MaxN], Cnt;

void Add(int U, int V) {
    Road[++Cnt] = (Edge) {V, Last[U]}, Last[U] = Cnt;
}

int Lowbit(int X) {
    return X & (-X);
}

int Tree[MaxN];
int N, M;

void Update(int X, int K) {
    while(X < MaxN) {
        Tree[X] += K;
        X += Lowbit(X);
    }
} 

int Sum(int X) {
    int Ans = 0;
    while(X) {
        Ans += Tree[X];
        X -= Lowbit(X);
    }
    return Ans;
}

char Or[MaxN], A[MaxN];
int Q[MaxN], Cur = 0, Ret = 0;

void Insert(char *S, int Root) {
    for(int i = 0; S[i]; i++) {
        if(S[i] == 'P') Q[++Ret] = Root; 
        else {
            if(S[i] == 'B') Root = Ac[Root].Fa;
            else {
                int Now = S[i] - 'a';
                if(!Ac[Root].Vis[Now]) Ac[Root].Vis[Now] = P, Ac[P].Fa = Root, P += 1;
                Root = Ac[Root].Vis[Now];
            }
        }
    Ac[Root].End = 1;
    }
}

void Build() {
    std::queue<int> Que;
    for(int i = 0; i < 26; i++) if(Ac[0].Vis[i]) Ac[Ac[0].Vis[i]].Fail = 0, Que.push(Ac[0].Vis[i]);
    while(!Que.empty()) {
        int Top = Que.front(); Que.pop();
        for(int i = 0; i < 26; i++) {
            int Vis = Ac[Top].Vis[i];
            if(Vis) {
                Ac[Vis].Fail = Ac[Ac[Top].Fail].Vis[i];
                Que.push(Ac[Top].Vis[i]);
            }
            else Ac[Top].Vis[i] = Ac[Ac[Top].Fail].Vis[i];
        }
    }
}

int Dfn[MaxN], Time = 0, R[MaxN];

void Dfs(int Now) {
    Dfn[Now] = ++Time;
    for(int i = Last[Now]; i; i = Road[i].Next) {
        int To = Road[i].To;
        Dfs(To);
    }
    R[Now] = Time;
}

int Tot[MaxN];
int Ans[MaxN];

int main() {
    scanf("%s", Or);
    Insert(Or, 0); Build();
    std::vector <Query> Ask[MaxN];
    for(int i = 1; i < P; i++) Add(Ac[i].Fail, i);
    Dfs(0); int Root = 0; scanf("%d", &N);
    for(int i = 0; i < N; i++) {
        int X, Y; scanf("%d%d", &X, &Y);
        Ask[Y].push_back((Query) {X, i});
    }
    Update(Dfn[0], 1);
    Ret = 0; 
    for(int i = 0; Or[i]; i++) {
        if(Or[i] == 'P') {
            Ret += 1;
            for(int j = 0; j < Ask[Ret].size(); j++) {
                int X = Q[Ask[Ret][j].X];
                Ans[Ask[Ret][j].Y] = Sum(R[X]) - Sum(Dfn[X] - 1);
            }
        }
        else if(Or[i] == 'B') Update(Dfn[Root], -1), Root = Ac[Root].Fa;
        else Root = Ac[Root].Vis[Or[i] - 'a'], Update(Dfn[Root], 1);
     }
    for(int i = 0; i < N; i++) printf("%d\n", Ans[i]);
}