回文自动机PAM小结
回文自动机PAM小结
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132136120
https://www.luogu.com.cn/problem/P5496
类似AC自动机，维护两个指针，nxt和fail
nxt表示当前回文串开头末尾都接a转移到哪
fail表示当前串最长broder
PAM关键点：一个回文串的broder一定也是回文串，而且所有回文子串（末尾相同）都可以用此方法构造
然后转移和AC自动机类似。
几个理解上的易错点：
-
fail[1]=0，代码上没写出来，但对于单个字符
a的fail应该是0，XaX匹配失败应该是尝试匹配XX -
应该先算fail在加入点。考虑
ab，b在失配过程中发现XX形式不行，然后fail到-1号点。如果已经加入就会自己匹配自己了。 -
计算长度应该由父亲+2转移过来，但num应该是由fail转移过来
-
1号点代表的是初始长度为-1
dfcc的PAM
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2026-06-16
算法复键——树状数组
算法复键——树状数组 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/162026675 树状数组怎么被我忘光了？？？ 1. 干什么的 简单来说，树状数组支持一下两种操作： 单点加 查询前缀和 →\to→ 区间和查询 如果我们记录的是差分数列，那样子可以也可以实现： 区间加 单点查询 不一定是求和，所有满足交换律的都可以用树状数组实现。比如区间积、区间XOR 2. 怎么实现 现在以单点加、求前缀和为例： 我们定义一种操作 lowbit...
2022-04-22
【GDOI2022PJD1T4 小学生计数题】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16180001.html D1T4 小学生计数题 题目 作为 GDOI 的组题人，小 Y 需要整理手中已有的题目，考虑它们的难度以及所考察的知识点，然后将它们组成数套题目。 小 Y 希望先能组出第一套题目，为了整套题目具有良好的区分度，在一套题目中： 所有题目的难度需要能排成等差数列；（也就是说，若将所有题目按难度从小到大排序，那么每相邻两题的难度的差相等，这个差叫做公差） 每道题目的难度都是公差的倍数，公差不为 0； 需要有不少于 LLL 道...
2022-04-25
【GDOI2022PJD2T3 教室的电子钟】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16191355.html D2T3 教室的电子钟 题目 为了迎接 GDOI，小蒟蒻学校所有教室的钟都换成了电子钟。电子钟会显示年月日时分秒的信息，每天的时间从 00:00:00 到 23:59:59。电子钟共有 14 个格子，共 14 × 7 = 98 个 LED 灯管组成。 具体来说，每个格子都是下面的十种状态中的一种，可以看到每个数字都是有 7 个 LED 灯管的亮暗状态呈现的： 这个钟的设计非常奇怪，每个灯管保持亮和保持暗的时候都是不消...
2023-08-18
因数、gcd等式子用莫比乌斯函数表示的一种简单方法
因数、gcd等式子用莫比乌斯函数表示的一种简单方法 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132355546 对于此式，可以发现，本质就是把T的质因子集合全部抽出来，划分成两个不交的集合。假设 TTT 的集合大小为 w(T)w(T)w(T) ，那么这个式子本质上就是 2w(T)2^{w(T)}2w(T) 现在考虑用积性函数的形式表示，我们对 ddd 进行唯一素数表示，发现对于 d1,d2d_1, d_2d1,d2 ，若他们的底数种类相同，指数不...
2022-04-28
【CF474D Flowers】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16203821.html 题目链接 题目 We saw the little game Marmot made for Mole's lunch. Now it's Marmot's dinner time and, as we all know, Marmot eats flowers. At every dinner he eats some red and white flowers. Therefore a dinner can be r...
2021-12-09
【Loj #10012. 「一本通 1.2 例 2」Best Cow Fences】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15669626.html 题目链接 题目 给定一个长度为 nnn 的非负整数序列 AAA ，求一个平均数最大的，长度不小于 LLL 的子段。 思路 先二分平均值。 然后是判断。 如何判断一段数中是否存在长度大于等于 LLL 且平均值大于某个数的子段呢？ 我们可以先让序列中的数都减去二分中的值，然后就转化为： 序列中是否存在长度大于等于 LLL 的字段和为正。 我们可以先构造一个前缀和。 假设我们当前算到序列中的第 iii 项，我们只需要在前 i−...