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

AC自动机

时间:2024-08-25 19:04:52浏览次数:11  
标签:nxt AC include int fail 自动机 节点

简单版

题目描述

给定 \(n\) 个模式串 \(s_i\) 和一个文本串 \(t\),求有多少个不同的模式串在文本串里出现过。
两个模式串不同当且仅当他们编号不同。

思路

我们可以将所有模式串存进 \(trie\) 树中,像这样:

此时如果我们朴素地查找,那显然会超时,因此我们可以使用类似 \(KMP\) 算法的思想,对于每个点都创建一个 \(fail\) 指针,表示与当前节点表示的字符串在\(trie\) 树中出他自己外的后缀最长的那个所在位置,就拿图来举例吧,对于节点 \(4\) 他的表示的字符串为 \(ABC\),它的除它自己外的后缀有 \(C\),\(BC\),在 \(trie\) 中它们都存在,于是我们取最长的 \(BC\) ,它在 \(7\) 号节点,所以 \(fail_4=7\)。

那怎么求 \(fail\) 呢?这个我们可以用广搜来实现,毕竟一个点的 \(fail\) 显然不会比这个点深。那么一个点的 \(fail\) 就是它父亲的 \(fail\) 对应的当前节点的字符,也就是说若设 \(v\) 为当前节点,\(u\) 为它的父节点,\(i\) 为 \(v\) 这个节点存的字符,那么就有 \(fail[v]=nxt[fail[u]][i]\)。特别地,如果 \(v\) 还没建立我们可以让 \(v\) 直接等于它的 \(fail\) 值。

有了 \(fail\) 后,一切就好办了,只需要将要匹配的文本串在 \(trie\) 中查找,每到一个节点就不断跳 \(fail\) 更新答案,毕竟当前节点能匹配上,那它的后缀自然能匹配上嘛。

注意事项

一定不要重复记录一个点的贡献。

代码

#include<iostream>
#include<bitset>
#include<string>
#include<cstring>
#include<queue>
using namespace std;
namespace AC{
	int nxt[1000010][26],cnt=0;
	int end[1000010],fail[1000010];
	queue<int>q;
	void insert(string s){
		int len=s.size();
		int u=0;
		for(int i=0;i<len;i++){
			if(!nxt[u][s[i]-'a']){
				nxt[u][s[i]-'a']=++cnt;
			}
			u=nxt[u][s[i]-'a'];
		}
		end[u]++;
		return;
	}
	void build(){
		queue<int>q;
		for(int i=0;i<26;i++){
			if(nxt[0][i]){
				q.push(nxt[0][i]);
			}
		}
		while(!q.empty()){
			int u=q.front();
			q.pop();
			for(int i=0;i<26;i++){
				if(nxt[u][i]){
					fail[nxt[u][i]]=nxt[fail[u]][i];
					q.push(nxt[u][i]);
				}else{
					nxt[u][i]=nxt[fail[u]][i];
				}
			}
		}
		return;
	}
	int query(string s){
		int u=0,ans=0;
		int len=s.size();
		for(int i=0;i<len;i++){
			u=nxt[u][s[i]-'a'];
			for(int j=u;j&&end[j]!=-1;j=fail[j]){
				ans+=end[j];
				end[j]=-1;
			}
		}
		return ans;
	}
}
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		string t;
		cin>>t;
		AC::insert(t);
	}
	AC::build();
	string s;
	cin>>s;
	cout<<AC::query(s)<<endl;
	return 0;
}

加强版

题目描述

给定 \(n\) 个模式串 \(s_i\) 和一个文本串 \(t\),求有多少个不同的模式串在文本串里出现过。
两个模式串不同当且仅当他们编号不同。

思路

这题跟前一题咋看区别并不大,很容易想到用数组记录答案,每匹配上一次就更新答案,但是这样做由于一个点会被访问不止一次,时间复杂度无法接受,因此需要优化。我们来分析一下,就拿前面那张图举例:

我们会发现当到达 \(4\) 时,我们会接着一连更新 \(4,7,9\),到 \(7\) 时又会更新一遍 \(7,9\)。很显然,问题就是出在这里,我们每个点不断被一次一次地更新,导致时间复杂度过大。因此,我们需要找到一种方法能够一次性统计一个点的答案。

我们可以把每个 \(fail\) 当作一条边建图,易证这是一个 \(DAG\),我们可以不用不断跳 \(fail\) 只需要标记当前点,再跑一遍拓扑排序,在拓扑排序的同时进行递推,这样每个点只会被更新一次,大大降低了复杂度。

代码

#include<iostream>
#include<queue>
#include<string>
#include<cstring>
using namespace std;
namespace AC{
	int nxt[12800][26],tot=0;
	int ind[12800],fail[12800],cnt[160];
	queue<int>q;
    void reset(){
        tot=0;
        memset(nxt,0,sizeof(nxt));
        memset(ind,0,sizeof(ind));
        memset(fail,0,sizeof(fail));
        memset(cnt,0,sizeof(cnt));
        return;
    }
	void insert(string s,int p){
		int len=s.size();
		int u=0;
		for(int i=0;i<len;i++){
			if(!nxt[u][s[i]-'a']){
				nxt[u][s[i]-'a']=++tot;
			}
			u=nxt[u][s[i]-'a'];
		}
		ind[u]=p;
		return;
	}
	void build(){
		queue<int>q;
		for(int i=0;i<26;i++){
			if(nxt[0][i]){
				q.push(nxt[0][i]);
			}
		}
		while(!q.empty()){
			int u=q.front();
			q.pop();
			for(int i=0;i<26;i++){
				if(nxt[u][i]){
					fail[nxt[u][i]]=nxt[fail[u]][i];
					q.push(nxt[u][i]);
				}else{
					nxt[u][i]=nxt[fail[u]][i];
				}
			}
		}
		return;
	}
	int query(string s){
		int u=0;
		int len=s.size();
		for(int i=0;i<len;i++){
			u=nxt[u][s[i]-'a'];
			for(int j=u;j;j=fail[j]){
				cnt[ind[j]]++;
			}
		}
        int ans=0;
        for(int i=1;i<=tot;i++){
            if(ind[i]){
                ans=max(ans,cnt[ind[i]]);
            }
        }
		return ans;
	}
}
string t[160];
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    while(cin>>n&&n){
        AC::reset();
        for(int i=1;i<=n;i++){
            cin>>t[i];
            AC::insert(t[i],i);
        }
        AC::build();
        string s;
        cin>>s;
        int ans=AC::query(s);
        cout<<ans<<"\n";
        for(int i=1;i<=n;i++){
            if(AC::cnt[i]==ans){
                cout<<t[i]<<"\n";
            }
        }
    }
    cout<<flush;
    return 0;
}

标签:nxt,AC,include,int,fail,自动机,节点
From: https://www.cnblogs.com/pengdave/p/18379340

相关文章

  • Python3.11二进制AI项目程序打包为苹果Mac App(DMG)-应用程序pyinstaller制作流程(App
    众所周知,苹果MacOs系统虽然贵为Unix内核系统,但由于系统不支持N卡,所以如果想在本地跑AI项目,还需要对相关的AI模块进行定制化操作,本次我们演示一下如何将基于Python3.11的AI项目程序打包为MacOS可以直接运行的DMG安装包,可以苹果系统中一键运行AI项目。MacOs本地部署AI项目首先确......
  • ACCESS Base64编码原理
    为了更详细地解释Base64编码的过程,我们可以从头开始逐步分解这个过程。假设我们有一段简单的ASCII文本"Hello",我们将详细展示如何将其转换为Base64编码。 1.获取文本的ASCII码首先,将"Hello"转换为其ASCII码值。每个字符的ASCII码如下:-'H'=72-'e'=101-......
  • patch-package|npm补丁修复
    可以用来修复依赖代码缺陷,或者按照自己需求做一点小东西做小改动可以,大改动最好还是fork仓库发包1.开发环境安装npmipatch-package--save-dev2.手动去node_module中修改(我要修改fastify的代码)3.修改完成后,为fastify生成补丁npxpatch-packagefastify4.加......
  • Triple Attack 题解
    直接暴力显然不可行。我们容易发现,变量\(T\)的增量以\(3\)为循环,一次循环会造成\(5\)的贡献,所以我们容易想到对每个\(a_i\)直接对\(5\)计算倍数和取余,然后对于余数分类讨论去增加,然后对于倍数部分统一增加即可。有些细节。Code#include<bits/stdc++.h>//#include......
  • [Javascript] Refactor blocking style code to stream style for fetching the strea
    WhenyouuseChatGPT,theresponsecomesinstream,sothatitcanappearsonscreenwheneverdatacomebackfromserver,wedon'tneedtowaitalldatacompletedthenshowingthedatatousers. Hereiscodewhichneedtobeimproved,becausethis......
  • 回文自动机小记
    构建口胡一下过程:\(fail\)边指向自己的最长回文后缀(偶根指向奇根)。定理:每添加一个字符,至多新增一个新的本质不同的回文串,且是所有回后缀中最长的。由此得出推论:本质不同的回文子串(回文自动机的点数)不超过|S|暴力跳终止链,找到第一个左侧有\(x\)的回文后缀\(v\)。......
  • AC 自动机 学习笔记
    前言本来时今年寒假学的,当时回家比较早没学完也没学明白,打模拟赛却多次用到,所以重学一下。原理与定义即字典树(trie树)加\(fail\)指针,\(fail\)指针等同于kmp的\(next\)数组,匹配前缀的最长后缀,\(fail\)指针单独拎出来构成一颗失配树(fail树)。插入同trie树,全部插完后......
  • delphi dxCameraControl控件(拍照)
    拍照演示DevExpressVCL组件之一 TdxCameraControlObjectHierarchy  Properties  Methods  Events 一个摄像头控件Unit dxCameraControl Syntax TdxCameraControl= class(TdxCustomCameraControl) Descrition 该控件允许您捕捉视频或图像从内......
  • Hitachi Vantara Programming Contest 2024(AtCoder Beginner Contest 368)- C
    题意概述有\(N\)个数,分别为\(H_1,H_2,H_3……H_N\)。你将使用初始化为\(0\)的变量\(T\)重复以下操作,直到所有数的值都变为\(0\)或更少。将\(T\)增加\(1\)。然后,减少最前方\(H_i\)值大于等于\(1\)的值。如果\(T\)是\(3\)的倍数,\(H_i\)的值会减少\(3\);......
  • [英语单词] feedback
    Embeddedcomputersandnetworksmonitorandcontrolthephysicalprocesses,usuallywithfeedbackloopswherephysicalprocessesaffectcomputationsandviceversa.https://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-72.pdffeedback的普遍意思是,......