首页 > 其他分享 >AC-automaton

AC-automaton

时间:2022-11-06 18:23:15浏览次数:65  
标签:10 AC ch int acam tot automaton

【模板】AC 自动机

posted on 2022-06-11 11:17:10 | under 模板 | source

template<int N,int M=26,int D='a'> struct acam{
	int ch[N+10][M],cnt[N+10],tot,fail[N+10];
	int sum[N+10],inn[N+10];
	int newnode(){return ++tot,cnt[tot]=fail[tot]=0,memset(ch[tot],0,sizeof ch[tot]),tot;}
	acam():tot(-1){newnode();}
	int insert(char *s){
		int len=strlen(s+1),u=0;
		for(int i=1;i<=len;i++){
			int &v=ch[u][s[i]-D];
			v?u=v:u=v=newnode();
		}
		return cnt[u]++,u;
	}
	void build(){
		queue<int> q;
		for(int i=0;i<M;i++) if(ch[0][i]) q.push(ch[0][i]);
		while(!q.empty()){
			int u=q.front();q.pop();
			for(int i=0;i<M;i++){
				if(ch[u][i]) fail[ch[u][i]]=ch[fail[u]][i],q.push(ch[u][i]);
				else ch[u][i]=ch[fail[u]][i];
			}
		}
	}
//	int query(char *s){
//		memset(vis,0,sizeof vis);
//		int len=strlen(s+1),u=0,res=0;
//		for(int i=1;i<=len;i++){
//			u=ch[u][s[i]-D];
//			for(int v=u;v&&!vis[v];v=fail[v]){
//				res+=cnt[v],vis[v]=1;
//			}
//		}
//		return res;
//	}
	void query(char *s){
		memset(sum,0,sizeof sum);
		memset(inn,0,sizeof inn);
		queue<int> q;
		int len=strlen(s+1),u=0;
		for(int i=1;i<=len;i++) sum[u=ch[u][s[i]-D]]++;
		for(int u=1;u<=tot;u++) inn[fail[u]]++;
		for(int u=1;u<=tot;u++) if(!inn[u]) q.push(u);
		while(!q.empty()){
			int u=q.front();q.pop();
			int v=fail[u];
			sum[v]+=sum[u];
			if(!--inn[v]&&v) q.push(v);
		}
	}
};

标签:10,AC,ch,int,acam,tot,automaton
From: https://www.cnblogs.com/caijianhong/p/16863292.html

相关文章

  • AcWing 95. 费解的开关
    第一个难点:如何枚举第一行的操作(指数类型的枚举,可以使用第一题的指数型枚举)这里使用二进制类型枚举11010=26反过来任何一个整数0-65536也可以用二进制表示0-31......
  • 基于PCM2706的USB-DAC(支持同轴、I²S输出)
    基于PCM2706的USB-DAC(支持同轴、I²S输出)简介:PCM2706是德州仪器公司的一款经典立体声16bitDAC解码芯片,集成HID人机控制接口与USBinterface,支持同轴信号输出(SPDI/F)、IIS数......
  • 关于 manacher 的一个小细节
    在该算法中,我们需要用到一个数组hw[i],代表i的最大回文半径。而且这个半径不包括i本身(若串为ccc则hw为1)。这时最终答案为最大的hw减一。为什么要减一呢?最终......
  • Mac安装RabbitMQ
    使用brew命令安装rabbitmq,首先必须安装HomeBrew/bin/zsh-c"$(curl-fsSLhttps://gitee.com/cunkai/HomebrewCN/raw/master/Homebrew.sh)"回车后根据提示执行,等待安......
  • Batch Normalization: Accelerating Deep Network Training by Reducing Internal Cov
    BN层只是从一定程度上解决了梯度衰减的问题但是并没有完全解决如果输入值的差距过大会导致模型加BN层后loss依旧无变化。代码:fromenumimportautofromscipy.ioimpo......
  • PLSQL中查询Oracle数据显示科学计数法的解决方法
    PL/SQL查询时,如果Number(17)以上的大数,会显示为科学计数法解决方法:TOOLS->PREFERENCES->WINDOWTYPE->SQLWINDOW下选中Numberfieldsto_char即可。......
  • 【机器学习】模型训练结果衡量指标准确率acc、精确率pre、召回率recall
    (49条消息)机器学习中准确率、精确率、召回率、误报率、漏报率、F1-Score、AP&mAP、AUC、MAE、MAPE、MSE、RMSE、R-Squared等指标的定义和说明_liveshow021_jxb的博客-CSD......
  • Jackson使用详解
    非常感谢原博主,参考声明:https://juejin.cn/post/6844904166809157639❝SpringMVC默认采用Jackson解析Json,尽管还有一些其它同样优秀的json解析工具,例如FastJson、G......
  • 使用Jackson生成和解析JSON
    参考声明:https://www.pudn.com/news/62eb6e90864d5c73ac50d924.html参考声明:https://zhuanlan.zhihu.com/p/65224789Jackson是目前使用非常广泛的JSON生成和解析工具......
  • 外设驱动库开发笔记48:MCP4725单通道DAC驱动
      在产品设计过程中,我们经常会遇到数模转换的应用需求。在本篇种我们就来讨论一下MCP4725单通道数模转换器的驱动设计与实现。1、功能概述  MCP4725是一个低功耗,高精......