搜索结果
查询Tags标签： 自动机，共有 43条记录-
算法学习—————PAM回文自动机
时隔一年，第一次学习新的算法 原理和AC自动机差不多 基本思想：两棵树分别代表奇偶在一个回文串两边同时填上相同字符可以得到另一个回文串，以此构建两棵树树上维护信息：节点表示的回文串为当前位置的最长回文串节点上维护当前位置最长回文串的长度，fail指针（当前回文…
2022/9/7 1:39:21 人评论 次浏览 -
回文自动机（回文树）学习笔记
回文自动机（回文树）学习笔记 前置知识 建议提前学习 Manacher 算法 和其他任何一种自动机，方便理解，不过不学问题应该也不大。 定义 回文自动机（PAM），也称回文树，是存储一个字符串所有回文子串的数据结构。 PAM 由转移边和后缀链接构成，它的每一个状态都代表着一…
2022/8/30 23:26:15 人评论 次浏览 -
ac自动机
模板 void insert() //建trie树 {int p = 0;for (int i = 0; str[i]; i ++ ){int t = str[i] - a;if (!tr[p][t]) tr[p][t] = ++ idx;p = tr[p][t];}cnt[p] ++ ; }void build() {int hh = 0, tt = -1;for (int i = 0; i < 26; i ++ )if (tr[0][i])q[ ++ tt] = tr[0][i]…
2022/8/23 6:52:48 人评论 次浏览 -
Trie数和AC自动机
字符串算法，随便学一下。 Trie树 字典树，用来求前缀的匹配。 比较简单，每一个字符都是一个节点，相同字符都是相同节点，然后就完了。 我们可以设这里插入的字符串分别是 abc cab bac bca这就是 Trie 构造出来的样子，是不是一下就懂了？我们查询的时候根据这个树跳就完…
2022/8/6 23:27:12 人评论 次浏览 -
AC 自动机
重新学 \(AC\) 自动机发现以前就像没见过一样…… 首先是一段经典的话：“\(AC\) 自动机是 \(trie\) 树上跑 \(kmp\)” 于是 \(AC\) 自动机的关键在于运用 \(nxt\) 进行匹配 由于这时的 \(nxt\) 形成一棵树形结构，可以将一些匹配问题转化为树上问题 如果 \(x\) 匹配到了文…
2022/7/26 23:23:46 人评论 次浏览 -
【模板】子序列自动机
link 其实感觉这玩意不应该叫什么自动机，这似乎就是一个个人yy出来的东西。。。 给定一个文本串和许多模式串，询问每个模式串是不是文本串的子序列。如果是询问字串的话直接上kmp即可，但子序列呢。考虑贪心，寻找文本中第一个和模式串第一个元素相同的元素位置，选择它…
2022/7/24 23:25:59 人评论 次浏览 -
java 进阶P-6.2+P-6.3
细胞自动机 CellularAutomation(细胞自动机)细胞自动机（英语：Cellular automaton），又称格状自动机、元胞自动机，是一种离散模型，在可算性理论、数学及理论生物学都有相关研究。它是由无限个有规律、坚硬的方格组成，每格均处于一种有限状态。整个格网可以是任何有限…
2022/6/24 14:21:54 人评论 次浏览 -
后缀自动机 SAM
struct NODE {int ch[26];int len,fa;NODE(){memset(ch,0,sizeof(ch));len=0;} }dian[MAXN<<1]; int las=1,tot=1; void add(int c) {int p=las;int np=las=++tot;dian[np].len=dian[p].len+1;for(;p&&!dian[p].ch[c];p=dian[p].fa)dian[p].ch[c]=np;if(!p)…
2022/6/12 23:23:53 人评论 次浏览 -
后缀自动机
（本文不适合初学者） SAM个人认为 SAM yyds希望有一天 SAM 能统治字符串界前置概念\(\operatorname{endpos}\) 集合表示一个子串在原串中出现的位置集合所有的子串通过 \(\operatorname{endpos}\) 分成一个个等价类构造每个节点代表一个子串集合（或者看成是一种状态），…
2022/6/4 23:50:13 人评论 次浏览 -
python第三方库AC自动机pyahocorasick的使用
pyahocorasick是一个快速且内存效率高的库，用于精确或近似多模式字符串搜索，这意味着您可以在某些输入文本中一次找到多个关键字符串出现。 字符串“索引”可以提前构建并保存到磁盘以便稍后重新发送。 pyahocorasick是用 C 语言实现的，并在 Python 3.6 及更高版本上进…
2022/4/27 1:16:39 人评论 次浏览 -
[学习笔记]基础字符串算法
这里使用“基础”仅代表整合一些篇幅小的算法与后续几篇大的字符串算法文章区别。 留给自己补科技树的时间越来越短了。 字符串哈希 容易实现，可以快速比对两个串是否相等。 一般可以使用自然溢出\(Hash\)。 注意使用非自然溢出时，应当把膜数取比字符串数量高一个数量级…
2022/2/21 14:26:35 人评论 次浏览 -
真菌元胞自动机Python实现
2021年美赛A题真菌元胞自动机Python实现 import matplotlib.pyplot as plt import random import numpy as np import matplotlib.animation as animationdef save_fungi_ca_gif(): # save the gif file to the pathtarget_gif_path = "E:/engineering space/figure…
2021/11/4 1:10:26 人评论 次浏览 -
真菌元胞自动机Python实现
2021年美赛A题真菌元胞自动机Python实现 import matplotlib.pyplot as plt import random import numpy as np import matplotlib.animation as animationdef save_fungi_ca_gif(): # save the gif file to the pathtarget_gif_path = "E:/engineering space/figure…
2021/11/4 1:10:26 人评论 次浏览 -
【模板】AC自动机
题意给定 \(n\) 个模式串 \(s_i\) 和一个文本串 \(t\) ，求有多少个不同的模式串在文本串里出现过。 两个模式串不同当且仅当他们编号不同。题解 AC 自动机，俗称在 Trie 上跑 KMP ，不能否定但也不能完全认同。 本篇题解并不详细，供己用，在板子里打了一点注释。 AC自动…
2021/10/4 23:15:07 人评论 次浏览 -
【模板】AC自动机
题意给定 \(n\) 个模式串 \(s_i\) 和一个文本串 \(t\) ，求有多少个不同的模式串在文本串里出现过。 两个模式串不同当且仅当他们编号不同。题解 AC 自动机，俗称在 Trie 上跑 KMP ，不能否定但也不能完全认同。 本篇题解并不详细，供己用，在板子里打了一点注释。 AC自动…
2021/10/4 23:15:07 人评论 次浏览
