AC自动机入门+模板 (HDU 2222)

2023-10-20 01:48
文章标签 模板 入门 hdu ac 自动机 2222

本文主要是介绍AC自动机入门+模板 (HDU 2222),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Aho-Corasick算法是多模式匹配中的经典算法
多模式匹配就是有多个模式串P1,P2,P3…,Pm,求出所有这些模式串在连续文本T1….n中的所有可能出现的位置。
步骤
1.建立模式的Trie
2.给Trie添加失败路径
3.根据AC自动机,搜索待处理的文本
重难点
构造失败指针
设这个节点上的字母为C, 沿着他父亲的失败指针走,直到走到 节点,他的儿子中也有字母为C的节点。然后把当前节点的失败指针指向那个字母也为C的节点。如果一直走到了root都没找到,那就把失败指针指向root。
  使用广度优先搜索BFS,层次遍历节点来处理,每一个节点的失败路径。  
  特殊处理:第二层要特殊处理,将这层中的节点的失败路径直接指向父节点(也就是根节点)。
例如(图片引用自网络)

模板 (HDU2222)
给几个关键字和一个模板串,求关键字在模板串中出现了几次

#include <bits/stdc++.h>
using namespace std;
struct Trie
{int next[500010][26],fail[500010],end[500010];int root,L;int newnode(){for(int i = 0;i < 26;i++)next[L][i] = -1;end[L++] = 0;return L-1;}void init(){L = 0;root = newnode();}void insert(char buf[]){int len = strlen(buf);int now = root;for(int i = 0;i < len;i++){if(next[now][buf[i]-'a'] == -1)next[now][buf[i]-'a'] = newnode();now = next[now][buf[i]-'a'];}end[now]++;}void build(){queue<int>Q;fail[root] = root;for(int i = 0;i < 26;i++)if(next[root][i] == -1)next[root][i] = root;else{fail[next[root][i]] = root;Q.push(next[root][i]);}while( !Q.empty() ){int now = Q.front();Q.pop();for(int i = 0;i < 26;i++)if(next[now][i] == -1)next[now][i] = next[fail[now]][i];else{fail[next[now][i]]=next[fail[now]][i];Q.push(next[now][i]);}}}int query(char buf[]){int len = strlen(buf);int now = root;int res = 0;for(int i = 0;i < len;i++){now = next[now][buf[i]-'a'];int temp = now;while( temp != root ){res += end[temp];end[temp] = 0;temp = fail[temp];}}return res;}void debug(){for(int i = 0;i < L;i++){printf("id = %3d,fail = %3d,end = %3d,chi [",i,fail[i],end[i]);for(int j = 0;j < 26;j++)printf("%2d",next[i][j]);printf("]\n");}}
};
char buf[1000010];
Trie ac;
int main()
{int T;int n;scanf("%d",&T);while( T-- ){scanf("%d",&n);ac.init();for(int i = 0;i < n;i++){scanf("%s",buf);ac.insert(buf);}ac.build();scanf("%s",buf);printf("%d\n",ac.query(buf));}return 0;
}

这篇关于AC自动机入门+模板 (HDU 2222)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/243804

相关文章

Spring Boot + MyBatis Plus 高效开发实战从入门到进阶优化(推荐)

《SpringBoot+MyBatisPlus高效开发实战从入门到进阶优化(推荐)》本文将详细介绍SpringBoot+MyBatisPlus的完整开发流程,并深入剖析分页查询、批量操作、动... 目录Spring Boot + MyBATis Plus 高效开发实战:从入门到进阶优化1. MyBatis

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

Python FastAPI入门安装使用

《PythonFastAPI入门安装使用》FastAPI是一个现代、快速的PythonWeb框架,用于构建API,它基于Python3.6+的类型提示特性,使得代码更加简洁且易于绶护,这篇文章主要介... 目录第一节:FastAPI入门一、FastAPI框架介绍什么是ASGI服务(WSGI)二、FastAP

基于Java实现模板填充Word

《基于Java实现模板填充Word》这篇文章主要为大家详细介绍了如何用Java实现按产品经理提供的Word模板填充数据,并以word或pdf形式导出,有需要的小伙伴可以参考一下... Java实现按模板填充wor编程d本文讲解的需求是:我们需要把数据库中的某些数据按照 产品经理提供的 word模板,把数据

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

poj3468(线段树成段更新模板题)

题意:包括两个操作:1、将[a.b]上的数字加上v;2、查询区间[a,b]上的和 下面的介绍是下解题思路: 首先介绍  lazy-tag思想:用一个变量记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2093 考试排名(sscanf)

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()",有时候又没有。而它也不会给我们提示。 这种情况下,就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和