首页 > 其他分享 >AC自动机

AC自动机

时间:2024-08-15 15:42:09浏览次数:15  
标签:AC int void 4010 fail 自动机 复杂度

AC自动机

AC自动机是以 \(Trie\) 的结构为基础,结合 \(KMP\) 的思想建立的自动机,用于解决多模式串(作为子串的串)匹配等任务。

  • 建\(tire\) 树,正常操作即可

  • 建\(fail\)树,如果当前节点失配,可以通过跳\(fail\) 快速转到一个可能有答案的位置,相当于\(kmp\)但是在树上考虑所有模式串的情况下,一段最大的前缀等于当前节点对应字符串的后缀。概念很好理解,问题在如何实现。下面是优化后的实现,不易被卡。

    	while(!q.empty())
    	{
    		int u=q.front();
    		q.pop();
    		for(int i=0;i<=25;i++)
    		{
    			if(!sh[u][i])sh[u][i]=sh[fail[u]][i]; //如果不存在当前点(失配),找它父亲u失配后的节点fail[u],将边连向fail[u]的这个儿子。可能觉得fail[u]不一定有这个儿子,fail[u]一定比u先被处理,所以sh[fail[u]][i]一定处理过指向存在的一个点,且这个点一定是我要的答案。
    			else 
    			{
    				q.push(sh[u][i]);
    				int v=fail[u];
    				fail[sh[u][i]]=sh[v][i];//存在当前点直接fail记为sh[fail[u]][i],道理与上面相同。
    			}
    		}
    	}
    

    像上面那样实现,不存在的点不需要暴力跳\(fail\) 可以直接用

例题:

P3808

裸板子,暴力跳\(fail\)即可。

#include <bits/stdc++.h>
using namespace std;
int n,sh[1000010][27],ans,tot,cnt[1000010],fail[1000010];
char ss[1000010];
void insert()
{
	scanf("%s",ss+1);
	int len=strlen(ss+1);
	int u=0;	
	for(int i=1;i<=len;i++)
	{
		if(!sh[u][ss[i]-'a'])
			sh[u][ss[i]-'a']=++tot;
		u=sh[u][ss[i]-'a'];
	}
	cnt[u]++;
	return ;
}
void getfail()
{
	queue<int> q;
	for(int i=0;i<=25;i++)
	{
		if(sh[0][i])
		{
			fail[sh[0][i]]=0;
			q.push(sh[0][i]);
		}
	}
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=0;i<=25;i++)
		{
			if(!sh[u][i])sh[u][i]=sh[fail[u]][i]; 
			else 
			{
				q.push(sh[u][i]);
				int v=fail[u];
				fail[sh[u][i]]=sh[v][i];
			}
		}
	}
}
void find()
{
	int u=0,len=strlen(ss+1);
	for(int i=1;i<=len;i++)
	{
		int k=sh[u][ss[i]-'a'];
		while(k&&cnt[k]!=-1)
		{
			ans+=cnt[k];
			cnt[k]=-1;
			k=fail[k];
		}
		u=sh[u][ss[i]-'a'];
	}
	return ;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		insert();
	getfail();
	fail[0]=0;
	scanf("%s",ss+1);
	find();
	printf("%d\n",ans);
	return 0;
}

P3796

与上一题相同,记录每个模式串的个数即可。

P5357

看似与前题相似,只需要处理相同字符串即可,交一发就发现会TLE。

为什么会出现这种情况?前两道题自动机上的每个点都只会对答案产生一次贡献,只计算一次,这道题,可能有多次计算,复杂度最坏为\(O(模式串长度 · 文本串长度)\)

考虑如何让本体与前几道题一样只经过一次,显然我们可以打上标记,标记每个点被询问多少次,不急着跳\(fail\) .最后从深度最深的点开始跳\(fail\) 累加更新,每个点只算一次。考虑\(fail\) 树是一个\(DAG\),用\(topu\) 确定顺序即可。

void topu()
{
	queue<int> q;
	for(int i=0;i<=tot;i++)
	if(in[i]==0)q.push(i);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		int l=bo[u].size();
		if(l)
		{
			int cur=0;
			while(cur<l)
			{
				cnt[bo[u][cur]]=siz[u];
				cur++;
			}				
		}
		int v=nxt[u];
		in[v]--; //提前保存入度
		siz[v]+=siz[u];
		if(in[v]==0)q.push(v);
	}
}

[P2292]([P2292 HNOI2004] L 语言 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))

首先有一个显然的\(dp\)

\[dp[i]=dp[j] \& [i,j是否一个单词] \]

复杂度为\(o(m|t|^3)\),完全过不去。

因为\(i,j\) 段大概率不是单词,所以对答案没贡献,我们要思考准确定位一个后缀是单词,跳\(ACAM\) 的的\(fail\)可以找所有后缀,我们跳\(fail\) 的同时判断他是否是单词结尾转移,复杂度可以达到\(O(m|s||t|)\),任然过不去。

观察到\(|s|\le 20\),是一个特别小的数据,可以直接状压为一个实数。对每个点储存这个点后缀是单词的长度集合。

做文本串第\(i\)位匹配时,\(x\)状压前\(i-1\)的\(f[i]\) (\(f[i]\)表示前i位是否都可以被理解,可以为1,不可以为0)

#include <bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int n,m,cnt,sh[4010][30],l[4010],fail[4010],g[4010],f[N];
char s[N];
bool bk[4010];
void insert(int k)
{
	int u=0;
	int len=strlen(s+1);
	for(int i=1;i<=len;i++)
	{
		int c=s[i]-'a';
		if(!sh[u][c])sh[u][c]=++cnt;
		u=sh[u][c];
	}
	bk[u]=1;
	l[u]=len;
	return ;
}
void getfail()
{
	queue<int> q;
	for(int i=0;i<=25;i++)
		if(sh[0][i])q.push(sh[0][i]),fail[sh[0][i]]=0;
	while(!q.empty())
	{
		int u=q.front();q.pop(); 
		for(int i=0;i<=25;i++)
		{
			if(!sh[u][i])sh[u][i]=sh[fail[u]][i];
			else
			{
				q.push(sh[u][i]);
				fail[sh[u][i]]=sh[fail[u]][i];
			}
		}
	} 
	for(int i=1;i<=cnt;i++)
	{
		int j=i;
		while(j)
		{
			if(bk[j]&&l[j]<=20)
				g[i]|=(1<<(l[j]-1));
			j=fail[j];
		} 	
	}
}
int find()
{
	
	int len=strlen(s+1),x=0,u=0;
	for(int i=1;i<=len;i++)
	{
		int c=s[i]-'a';
		u=sh[u][c];
		x=((x<<1)|f[i-1])&((1<<20)-1);//x的第0位存的是i-1,第1位存的是i-2,...
		f[i]=(x&g[u])!=0;//g[u]的第0位存后缀长度为1是否w为单词...,g[u]与x的相同位置是对应,拼起来是s,x&g[u]!=0,说明有一位个g[u]和x都为1,这个长度断开符合题目要求
	}
	for(int i=len;i>=1;i--)
		if(f[i])return i;
	return 0;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s+1);
		insert(i);
	}
	getfail();f[0]=1;
	while(m--)
	{
		scanf("%s",s+1);
		printf("%d\n",find());
	}
	return 0;
} 

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

第一眼暴力,用打印的字符串建\(ACAM\) 询问的时候从\(0\)到\(y\) 的每个点暴力跳\(fail\) 统计\(x\) 的个数。

时间复杂度显然过不去。考虑刚才实际在干什么,一条路径上的点跳\(fail\) 找\(x\),在\(fail\) 树上看,只有\(x\)的子树内在\(y\)路径上的点有贡献。将根到\(y\)的路径的值设为1,统计\(x\)的子树和。

但还是不行,直接做还是超时,可以把询问离线,用树状数组维护

#include <bits/stdc++.h>
using namespace std;
const int N=100005;
int n, m,tot1,cnt,bk[N],fa[N],sh[N][30],bit[N],fail[N],tot,st[N],ed[N],ans[N],f[N];
char s[N];
struct node
{
    int x,id;
    node(int X=0,int I=0) : x(X) , id(I) {}
};vector<node> g[N];
struct edge
{
    int v,next;
    edge(int V=0,int N=0) : v(V) , next(N) {}
}e[2*N]; 
vector<int> ve[N];
void link(int u,int v)
{
    ve[u].push_back(v);
    ve[v].push_back(u);
}
void dfs(int u,int ff)
{
    st[u]=++tot;
    for(int i=0;i<ve[u].size();i++)
    {
        int v=ve[u][i];
        if(v==ff)continue;
        dfs(v,u);
    }
    ed[u]=tot;
    return ;
}
queue<int>q;
void getfail()
{
    for(int i=0;i<=25;i++)
    {
        if(sh[0][i])fail[sh[0][i]]=0,q.push(sh[0][i]); // 这里的0是根节点的编号;
    }
    while (!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<=25;i++)
        {
            if(!sh[u][i])sh[u][i]=sh[fail[u]][i];
            else
            {
                q.push(sh[u][i]);
                fail[sh[u][i]]=sh[fail[u]][i];
            }
        }
    }
    for(int i=1;i<=cnt;i++)
    {
        int u=i;
        int v=fail[i];
        link(u,v); 
    }
    return ;
}
int lowbit(int x)
{
    return x&(-x);
}
void modify(int x,int y)
{
    for(;x<=tot;x+=lowbit(x))
        bit[x]+=y;
    return ;
}
int ask(int x)
{
    int sum=0;
    for(;x>0;x-=lowbit(x)) sum+=bit[x];
    return sum;
}
int main() 
{
    scanf("%s",s+1);
    int len=strlen(s+1),now=0;
    for(int i=1;i<=len;i++)
    {
        if(s[i]>='a'&&s[i]<='z')
        {
            int c=s[i]-'a';
            if(!sh[now][c])sh[now][c]=++cnt,fa[cnt]=now;
            now=sh[now][c];
        }
        if(s[i]=='P')bk[++n]=now;
        if(s[i]=='B')now=fa[now];
    }
    getfail();
    dfs(0,0);
    scanf("%d",&m); 
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        g[y].push_back(node(x,i));
    }
    now=0;
    for(int i=1,j=0;i<=len;i++)
    {
        if(s[i]>='a'&&s[i]<='z')
        {
            int c=s[i]-'a';
            now=sh[now][c];
            modify(st[now],1);
        }
        if(s[i]=='P')
        {
            j++;
            for(int k=0;k<g[j].size();k++)
            {
                int x=g[j][k].x;
                ans[g[j][k].id]=ask(ed[bk[x]])-ask(st[bk[x]]-1);
            }
        }
        if(s[i]=='B')
        {
            modify(st[now],-1);
            now=fa[now];
        }     
    }
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}

标签:AC,int,void,4010,fail,自动机,复杂度
From: https://www.cnblogs.com/storms11/p/18361061

相关文章

  • SpringBoot优雅的封装不同研发环境下(环境隔离)RocketMq自动ack和手动ack
    1.RocketMq的maven依赖版本:<dependency><groupId>org.apache.rocketmq</groupId><artifactId>rocketmq-spring-boot-starter</artifactId><version>2.3.0</version></dependenc......
  • React 高德地图 进京证 路线规划 问题小记
    一、加载问题用高德地图做了个进京证路线规划的功能,官网也是有React代码示例。但是吧,这个Demo有问题,地图是能加载成功,但是其他功能再用map这个变量肯定不行,果不其然是null,处理也简单,把公共变量都管理起来就行了。const[map,setMap]=useState(null);const[AMap,setAMa......
  • Jetpack Compose学习(13)——Compose生命周期及副作用函数
    原文:JetpackCompose学习(13)——Compose生命周期及副作用函数-Stars-One的杂货小窝此文建议需要了解kotlin的lambda表达式使用和协程基础使用,不然可能会有些阅读困难本篇算是参考他人文章,按照自己理解重新总结了下吧,偏理论生命周期Composable组件都是函数,Composable......
  • TeeChart.NET 4.2024.7.29 Crack
    Versatilenative.NETCharting,MapandGaugecontrolTheTeeChartNETProEditionisaNugetbasedChartingcontroldesignedtoofferinstantchart,mapandgaugecapabilitiestoyourNETapplication.Withdozensofcharttypes,statisticalfunctionsand......
  • milvus-backup安装部署
    环境:OS:Centos7milvus:2.4.6standalone部署milvus-backup:0.49 1.官网:https://milvus.io/docs/milvus_backup_cli.md 2.下载地址:https://github.com/zilliztech/milvus-backup/releases  3.解压压缩包[root@host135milvus_backup]#mkdir-p/opt/milvus_backup#......
  • 易基因:RNA修饰N4-乙酰胞苷(ac4C)的调控机制、检测方法及其在癌症中的作用最新研究进展
    大家好,这里是专注表观组学十余年,领跑多组学科研服务的易基因。N4-乙酰胞苷(ac4C)是一种高度保守的化学修饰,广泛存在于真核和原核生物RNA中,如tRNA、rRNA和mRNA。这种修饰与多种人类疾病显著相关,尤其是癌症,其形成主要依赖于N-乙酰转移酶10(NAT10)(唯一已知ac4C的writer蛋白)的催化活性。......
  • oracle练习2024.08.15
    --1.创建一个名为‘EMP_DETAILS_VIEW’的只读视图,包含各个员工的员工编号、员工名、职位编号、职位名称、部门编号、国家信息和区域信息:createviewemp_details_viewasselect   e.employee_idasemployee_id,  e.first_name||''||e.last_nameasemployee......
  • windows-g下载js库使用时报错:无法加载文件 D:\code\node\node_global\create-reac
    无法加载文件D:\code\node\node_global\create-react-app.ps1,因为在此系统上禁止运行脚本。有关详细信息,请参阅https:/go.microsoft.com/fwlink/?LinkID=135170中的about_Execution_Policies。当我们在windows上-g(全局)安装一个js库时,执行会报这个错误,然后我们看......
  • Flutter项目移动端SQLite升级指南:解决json_extract函数缺失问题
    引言在Flutter移动端项目中依赖于SQLite的高级功能(如json_extract),在低版本的Android系统上部署时,可能会遇到函数不支持的问题。本文将指导你如何通过升级项目中使用的SQLite版本来解决这一问题。前置条件Flutter项目使用sqflite:^2.3.3+1进行SQLite数据库操作。IMBoyA......
  • 气象资料实时自动更新(CIMSS - West Pacific)
    目录UpperLevelWindsLowerLevelWindsUpperDivergenceLowerConvergenceWindShearShearTendency850mbVorticityUpperLevelWindsLowerLevelWindsUpperDivergenceLowerConvergenceWindShearShearTendency850mbVorticity......