首页 > 其他分享 >P3808 【模板】AC 自动机(简单版)

P3808 【模板】AC 自动机(简单版)

时间:2022-10-11 20:24:11浏览次数:80  
标签:AC int ++ vis P3808 fail 节点 模板

P3808
KMP用来求单模式串的匹配,AC自动机用来求多模式串的匹配。
就是给你n个模式串,再给你一个文本串,求有多少个模式串在文本串中出现过。
AC自动机的数据结构基于trie数,像KMP的nxt数组一样维护失配指针fail(寻找fail的过程是用bfs实现的),查询过程中不断向下匹配,匹配不了就往fail指针方向走。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
struct Trie {
	int fail;//失配指针 
	int vis[30];//子节点的位置编号 
	int End;
}AC[N];
int n, tot = 0;
string s;
void build(string s) {
	int len = s.length();
	int p = 0;
	for (int i = 0; i < len; i ++) {
		if (AC[p].vis[s[i] - 'a'] == 0)
			AC[p].vis[s[i] - 'a'] = ++ tot;
		p = AC[p].vis[s[i] - 'a'];
	}
	AC[p].End ++;
}
void getfail() {
	queue<int> q;
	for (int i = 0; i < 26; i ++) {//处理第二层失配指针 
		if (AC[0].vis[i] != 0) {//该节点存在 
			AC[AC[0].vis[i]].fail = 0;//第二层都要指向根节点 
			q.push(AC[0].vis[i]);
		}
	}
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int i = 0; i < 26; i ++) {
			if (AC[u].vis[i] != 0) {//该节点存在 
				AC[AC[u].vis[i]].fail = AC[AC[u].fail].vis[i];
				//令v = AC[u].vis[i] v是u的儿子,v的fail指向u的fail的相同字母的儿子 
				q.push(AC[u].vis[i]);
			}
			else AC[u].vis[i] = AC[AC[u].fail].vis[i];
			//节点不存在就直接将u的儿子节点指向u的fail的相同字母的儿子
		}
	}
}
int query(string s) {//AC自动机匹配 
	int len = s.length();
	int p = 0, ans = 0;
	for (int i = 0; i < len; i ++) {
		p = AC[p].vis[s[i] - 'a'];
		for (int k = p; k && AC[k].End != -1; k = AC[k].fail) {
			ans += AC[k].End;
			AC[k].End = -1;//标记已走过 
		}
	}
	return ans;
}
int main() {
	int T;
	scanf("%d", &T);
	while (T --) {
		memset((void *) &AC, 0x00, sizeof(AC));
		tot = 0;
		scanf("%d", &n);
		for (int i = 1; i <= n; i ++) {
			cin >> s;
			build(s);
		}
		AC[0].fail = 0;//结束标志(根节点的失配指针一定指向自己)
		getfail();//求失配指针 
		cin >> s;
		cout << query(s) << '\n';
	} 
	return 0;
}

image

标签:AC,int,++,vis,P3808,fail,节点,模板
From: https://www.cnblogs.com/YHxo/p/16782427.html

相关文章

  • 11g rac添加数据文件至本地文件系统的异常处理演练
    文档课题:11grac添加数据文件至本地文件系统的异常处理演练.系统:centos7.964位数据库:11.2.0.464位环境:rac(双节点)+dg应用场景:巡检客户一套核心数据库时,发现存在一个数......
  • ARC150D Removing Gacha(组合)
    ARC150DRemovingGacha有一棵\(N\)个白点的树根为\(1\),每次等概率随机选一个到\(1\)的路径上有白点的点涂黑,问期望几次整棵树被涂黑。模\(998244353\)。CODE首先......
  • oracle数据泵
    /*1)逻辑备份恢复:数据泵2)物理备份恢复:Rman数据泵技术(源端-》目标端)源端启动DataPumpJob(expdp)目标端启动DataPumpJob(impadp)1)数据泵核心部分程序包......
  • [转] webpack 中的 loader
      安装css的loader npmistyle-loadercss-loader-D ......
  • DataCore PlgIn for vCenter 3.0 SETTINGs
    第1章 VMwarevSphere3.0Plug-In只需要4步骤,可以在vCenterClient配置一颗存储,可具备高可用性,Multipath-RoundRobin,HighCaching...etc是不是很有趣。1.1 概述VMware......
  • 《基于Apache Flink的流处理》读书笔记
            前段时间详细地阅读了《ApacheFlink的流处理》这本书,作者是FabianHueske&VasilikiKalavri,国内崔星灿翻译的,这本书非常详细、全面得介绍了Flink流处......
  • 系列篇|编写一个翻转事件极性的package
    上次推送中我们已经能够利用现成的角点检测代码,完成事件相机数据的角点检测,并调用了rpg_dvs_ros这个package进行了显示。这次我们自己完成一个package,实现一个简单的功能:将......
  • 源码角度了解Skywalking之服务端OAP对Trace的处理
    源码角度了解Skywalking之服务端OAP对Trace的处理从前几篇的文章我们知道Skywalking对Trace信息进行生成收集后,将TraceSegment对象转换为UpstreamSegment对象,通过GRPC发送......
  • docker和Namespace技术介绍
    一、docker介绍Docker是基于linux内核实现,Docker最早采用LXC技术(LinuXContainer的简写,LXC是Linux原生支持的容器技术,可以提供轻量级的虚拟化,可以说d......
  • [模板]点分治
    洛谷p3806code#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintmaxn=1e5+7;constintinf=1e7;intn,m,maxp[maxn],siz[......