AC自动机
-
c/c++语言开发共享洛谷P3763 [TJOI2017]DNA(后缀数组 RMQ)
题意 “题目链接” Sol 这题打死我也不会想到后缀数组的，应该会全程想AC自动机之类的吧 但知道这题能用后缀数组做之后应该就不是那么难了 首先把$S$和$S0$拼到一起跑，求出Height数组 暴力枚举每个后缀是否能成为答案。 具体来说，每次比较当前后缀和$S_0$的lcp，如果长度$ using …
-
c/c++语言开发共享[luogu2292][L语言]
思路 这道题我用的是AC自动机的做法。 先把子串挂到tried树上，在单词结尾打标记的时候，标记的是当前单词的长度。然后去上面查询母串的时候，每查询到一个单词，就建立一条 …
-
c/c++语言开发共享[AC自动机][学习笔记]
用途 AC自动机适用于一类用多个子串在模板串中匹配的字符串问题。 也就是说先给出一个模板串，然后给出一些子串。要求有多少个子串在这个模板串中出现过。 …
-
c/c++语言开发共享简单版AC自动机
简单版$AC$自动机 学之前听别人说起一直以为很难，今天学了简单版的$AC$自动机，感觉海星，只要理解了$KMP$一切都好说。 前置知识： “$KMP$” （有链接） 前置知识：$Trie$树 字典树（$Trie$树）比较简单，就是把许多个单词通过树连接起来。每个点记录一下儿子个数以及是否是单词结尾 …
-
c/c++语言开发共享P3121 [USACO15FEB]审查(AC自动机)
题目： “P3121 [USACO15FEB]审查（黄金）Censoring (Gold)” 解析： 多字符串匹配，首先想到AC自动机 建立一个AC自动机 因为有删除和拼接这种操作，考虑用栈维护 顺着文本串匹配的方向走，将经过的节点放入栈中，若匹配到一个模式串，就将这个模式串弹出，从栈顶开始继续走 …
-
c/c++语言开发共享CF1207G Indie Album
“题目链接” problem 有$n$个字符串,对于第$i$个字符串通过以下两种方式中的一个给出。 1. $1; c$，该字符串只含一个字符$c$。 2. $2 x c$,该字符串为第$x(1le x include include include include include inclu …
-
[PHP教程] AC自动机 分享
能高效地匹配字符串，具体原理就不搬了，这边给出PHP的实现代码: <?php class AcAutomation { private $root; public funct…