简单版题目描述给定\(n\)个模式串\(s_i\)和一个文本串\(t\)，求有多少个不同的模式串在文本串里出现过。两个模式串不同当且仅当他们编号不同。思路我们可以将所有模式串存进\(trie\)树中，像这样：此时如果我们朴素地查找，那显然会超时，因此我们可以使用类似\(KMP\)算法

构建口胡一下过程：\(fail\)边指向自己的最长回文后缀（偶根指向奇根）。定理：每添加一个字符，至多新增一个新的本质不同的回文串，且是所有回后缀中最长的。由此得出推论：本质不同的回文子串（回文自动机的点数）不超过|S|暴力跳终止链，找到第一个左侧有\(x\)的回文后缀\(v\)。

AC自动机查漏补缺前言今年1月份学过一次，当时自以为掌握得很好，实际上就是依托答辩。而且还有很多地方是有严重误导性的。所以这篇查漏补缺就是记录一下自己对AC自动机尚不完全掌握的地方。并对之前的那篇不太正确的题解进行纠正。因此，在这样的背景下，这篇文章注定就不是给初

P2444[POI2000]病毒题目核心是多模式匹配，所以考虑用对所有模式串建立AC自动机。我们把自动机上，存在一个模式串作为前缀的节点，称作“危险节点”。如果无限长的安全代码存在的话，匹配过程中Trie图上一定有节点会经过多次，即存在环；而且经过的所有节点都不是“危险节点”，否则就包含

P4052[JSOI2007]文本生成器正难则反，我们发现用总字符串个数\(26^m\)，减去不可读的字符串个数，就是答案。要使一个字符串不可读，就不能让任何模式串在其中出现。如果某个主串的第\(i\)位与自动机的节点\(j\)相匹配，那么如果状态\(j\)包含模式串（即有一个前缀是一个模式串），那么不管主

UVA1127WordPuzzles我们对模式串建立AC自动机，然后就比较板子了，只需要把\(8\)个方向都跑一遍匹配就可以了。时间复杂度是\(O(T\times8nm)\)。注意输入是大写字母。点击查看代码#include<bits/stdc++.h>#defineK1010//模式串个数&矩阵长宽#defineN1000010//节点个

AC自动机前言我觉得AC自动机这种东西非常抽象，有必要写一篇博客来整理一下，以加深理解。概况AC自动机是以Trie树的结构为基础，结合KMP思想建立的自动机，用于解决多模式串匹配等任务。一般来说，建立一个AC自动机有两个步骤：把所有的模式串建成一颗Trie树。用KMP的思想对

AC自动机AC自动机是以\(Trie\)的结构为基础，结合\(KMP\)的思想建立的自动机，用于解决多模式串(作为子串的串)匹配等任务。建\(tire\)树，正常操作即可建\(fail\)树，如果当前节点失配，可以通过跳\(fail\)快速转到一个可能有答案的位置，相当于\(kmp\)但是在树上考虑所有模式串

考虑暴力怎么做。一个很自然的想法就是枚举每个模式串，并将当前枚举到的模式串作为文本串，然后内层循环再依次枚举模式串，看每个模式串在文本串中出现了多少次发现上述过程与AC自动机的匹配很像，于是建立AC自动机，将每个串都放在AC自动机上跑query，当前跑到的u就代表这个串的一个前缀，然

备注：我不知道fail会不会和什么东西重名。（因为感觉这个单词挺完整的）自动机的概念不是很清楚自动机的概念。暂且认为：自动机是一个有向图。点（状态）代表字符串（可能不止一个），边（转移）（可能）带一个字符，表示在字符串的末尾加上这个字符后到达的状态。有一个源点（PAM有两个），代表初始状态。有

树上高斯消元给你一颗树，某些点为终止结点，求从每个点开始随机游走走到某个终止节点的期望时间。从叶子开始将\(f(u)\)表示为\(k(u)f(\text{fa}(u))+b(u)\)，带回\(f(\text{fa}(u))\)的方程中将\(f(u)\)消掉即可。DAG上高斯消元可重集/reset有一个可重集\(S\)，每一

P3966[TJOI2013]单词用\(p[i]\)来表示经过节点\(i\)的字符串个数。那么节点\(u\)的答案就是fail树上，以\(u\)为根的子树的\(p\)之和。由于我们已经计算了\(p[i]\)，所以字符串\(i\)作为模式串本身&模式串前缀的情况已经考虑了。还需考虑\(i\)作为模式串后缀的情况，而只有fail树上

P2292[HNOI2004]L语言注：下文中，\(s[l\simr]\)表示截取字符串\(s\)的第\(l\)个字符到第\(r\)个字符。文字描述的字符串下标从\(1\)开始，但代码实现从\(0\)开始。我们建出AC自动机后，有一个比较暴力的思路。我么用\(f[i]\)表示待查找字符串\(t\)的长度为\(i\)前缀是否满足

今天发现一个奇怪的现象，前端请求后端服务多次后会超时一次，经过多次验证确定是大概10s左右就会超时一次，检查后端服务，发现其中一个节点已经夯死。但是我们的nginx负载均衡策略是轮询机制，按照配置来看应该是每隔一次请求轮询到失败的节点时超时一次才对。为什么是每隔10s超时一次呢？

1.KMP自动机1.1内容KMP自动机本质上就是单串的AC自动机。我们定义转移函数为：\[\delta(i,c)=\begin{cases}\delta(\pi_i,c)&s_{i+1}\not=c\\i+1&s_{i+1}=c\end{cases}\]其实也就是模拟了KMP的整个过程。1.2应用自动机上跑dp是最常见的应用，一般会有一

配置：Gigadevice闪存，Openwrt官方说明里这个型号闪存存在变砖风险，为求稳使用immortal改版固件。参考：https://openwrt.org/toh/qihoo/360t7_1.0固件：https://www.right.com.cn/forum/thread-8263340-1-1.htmlUboot：主要流程：拆外壳，焊接ttl官方固件降级低版本启动串口调试，出现提

AC自动机用于解决多模匹配问题。P3808【模板】AC自动机（简单版）询问所有模式串在文本串中出现的总次数。自动机上节点记录word表示此处为结尾的单词数。//名字空间封装好的AC自动机namespaceAC{ inttr[maxn][26],tot; intword[maxn],fail[maxn]; /* 失配指针

aaa今天字符串专题1）KMP思想是对于每一位求出最长的后缀等于前缀的长度next周期：字符串：【】【】【】【】【不完整周期】【】就是周期有一个周期就是串长减去next，所有周期长度都是最小周期的倍数；如果串不是最小周期的倍数，则这个串没有循环节。【NOI2014动物园】点击

[COCI2015-2016#5]OOP（Trie）P6727[COCI2015-2016#5]OOP-洛谷|计算机科学教育新生态(luogu.com.cn)正反串分别建Trie，可以搞出两个dfn区间，加之长度限制，三维数点。有\(O(n\logn)\)做法。将字典串\(S[1..m]\)，对所有\(1\leqi\leqm\)，将\(S[i+1,m]\)的hash值插入

PhpSpreadsheet解析Excel文件安装PhpSpreadsheet通过Composer安装了PhpSpreadsheet：composerrequirephpoffice/phpspreadsheet控制器ExcelController<?phpnamespaceapp\controller;usethink\facade\Db;usethink\facade\Request;usethink\facade\View;use

对于这种子串问题，且有多个基础串，一个比较直观的想法就是先上个广义SAM。考虑SAM与字典序如何联系上。因为跳\(\operatorname{fail}\)相当于是删除子串的一个前缀，直接这样子明显是不行的，因为跳了\(\operatorname{fail}\)字典序没有一个很直观地表示。但是反过来考虑反串，

preface第一次写ACAM模版是2023.7.02，现在重新回顾了一下，还是有不少新的理解的，或者说一些概念更加清晰了。1.引入思考这样一个问题：给若干模式串，求询问串中出现了多少个模式串。暴力肯定是一一比对，复杂度是\(O(n^2)\)以上的，可以哈希一下，那复杂度就是\(O(n^2)\)。回想

1.引入1.1.问题描述给定一个长度为\(n(1\len\le10^5)\)的字符串和\(m\)个模式串\(s_1,\cdots,s_m\)，求问字符串中出现了多少个模式串。\(\sums_i\le10^5\)。1.2.解法考虑当\(m=1\)的情况，直接跑KMP就可以了。但是如果\(m\)特别大时，跑KMP的复杂度

0.Painter’sStudio(POI1998)首先找规律。发现这个分形是每次平分，考虑二进制。容易发现\(a_{i,j}=1\)的条件是不存在任意\(i\)使得\(a_i<b_i\)。考虑平移之后。\((i,j)\rightarrow(i+x,j+y)\)都要是\(1\)。问题转化。\(f_{i,p,q}\)表示从低往高第

manacher马拉车通过在每个字符间插入一个特殊字符，使得字符串长度为奇数，从而保证每个字符都有中心。在每个中心记录回文串的长度。马拉车的扩展方式和\(Z\)函数类似。都是通过映射之前已经算过的位置，然后尽可能的向右扩展。复杂度\(O(n)\)通常马拉车的题目统计回文串需要与其他