LG5357 「模板」AC自动机（二次加强版） AC自动机+fail树

问题描述

题解

不是fail树的AC自动机复杂度是假的。

把AC自动机搞出来，建立Trie树，树上爆搜一遍就好了。

\(\mathrm{Code}\)

#include<bits/stdc++.h>

using namespace std;

template <typename Tp>

void read(Tp &x){

	x=0;char ch=1;int fh;

	while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();

	if(ch=='-') ch=getchar(),fh=-1;

	else fh=1;

	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

	x*=fh;

}

int root,ch[200007][26],tot,n;

char s[2000003];

int pos[200007],val[200007],fail[200007];

int m,ed[200007];

int chk(char s){

	return s-'a';

}

void insert(int x){

	int p=root;

	for(int i=1;i<=n;i++){

		int k=chk(s[i]);

		if(!ch[p][k]) ch[p][k]=++tot;

		p=ch[p][k];

	}

	++ed[p],pos[x]=p;

}

void query(){

	int p=root;

	for(int i=1;i<=n;i++){

		p=ch[p][chk(s[i])];

		++val[p];

	}

}

void build(){

	queue<int>q;

	for(int i=0;i<26;i++){

		if(ch[root][i]) q.push(ch[root][i]);

	}

	while(!q.empty()){

		int x=q.front();q.pop();

		for(int i=0;i<26;i++){

			if(ch[x][i]) fail[ch[x][i]]=ch[fail[x]][i],q.push(ch[x][i]);

			else ch[x][i]=ch[fail[x]][i];

		}

	}

}

int Head[200007],Next[200007],cnt,to[200007];

void add(int x,int y){

	to[++cnt]=y,Next[cnt]=Head[x],Head[x]=cnt;

}

int size[200007];

void dfs(int x){

	size[x]=val[x];

	for(int i=Head[x];i;i=Next[i]){

		dfs(to[i]);size[x]+=size[to[i]];

	}

}

int main(){

	ios::sync_with_stdio(0);

	cin>>m;

	for(int i=1;i<=m;i++){

		cin>>(s+1);n=strlen(s+1);

		insert(i);

	}

	cin>>(s+1);n=strlen(s+1);

	build();query();

	for(int i=1;i<=tot;i++) add(fail[i],i);

	dfs(root);

	for(int i=1;i<=m;i++) cout<<size[pos[i]]<<endl;

	return 0;

}

巴特西

LG5357 「模板」AC自动机（二次加强版） AC自动机+fail树

问题描述

题解

\(\mathrm{Code}\)

最新文章

热门文章