broder剃头去尾的新broder
broder剃头去尾的新broder
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135122233
若红色为1串的broder，则显然黄串为2串的broder
因此broder在剃头去尾
可以用于均摊分析
题目：POI2012」Prefixuffix
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2022-01-12
【P4551 最长异或路径】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15792154.html 题目链接 题目 给定一棵 nnn 个点的带权树，结点下标从 111 开始到 nnn。寻找树中找两个结点，求最长的异或路径。 异或路径指的是指两个结点之间唯一路径上的所有边权的异或 思路 预处理每个点到根节点路劲的异或和，建一棵01trie树。 对于每个节点，在trie树上找离它最远的节点，最后取个 max\maxmax 值即可。 总结 这道题应该也算两个经典问题的集合吧？ 首先求树上两个节点之间路径的异或和，这是一个非...
2022-01-16
【P3538 [POI2012]OKR-A Horrible Poem】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15810272.html 题目 原题来自：POI 2012 给出一个由小写英文字母组成的字符串 S，再给出 q 个询问，要求回答 S 某个子串的最短循环节。 如果字符串 B 是字符串 A 的循环节，那么 A 可以由 B 重复若干次得到。 思路 首先，我们如果有三点： 一个字符串的循环节必然是字符串长度的约数 循环节的倍数如果长度还是字符串长度的约数，那么他也是循环节 如果一个长度 iii 是字符串循环节长度，那么 [l,r−i][l, r-i]...
2022-01-16
【P6739 [BalticOI 2014 Day1] Three Friends】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15809039.html 题目链接 题目 有一个字符串 SSS，对他进行操作： 将 SSS 复制为两份，存在字符串 TTT 中 在 TTT 的某一位置上插入一个字符，得到字符串 UUU 现在给定 UUU，求 SSS。 思路 哈希 先预处理这个字符串的哈希前缀和，然后枚举插入位置，这时候把左右的 SSS 求出来，看看是否相同。 需要注意的是，题目是说 SSS 不是唯一的猜输出 NOT UNIQUE，也就是说如果有多种切断方式但 SSS 一样还是...
2026-06-17
算法复键——AC自动机
算法复键——AC自动机 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/162074359 什么是AC自动机： 在Trie上跑kmp 核心思想：构建fail树。fail[u]指向一个节点，表示这个节点具有和u所在节点所代表串的最长公共后缀。 核心代码： 12345678910111213141516171819void bfs() { int i, j; q.push(1); fail[1] = 0; fail[0] = 1; // 根节点失配指向...
2026-07-09
字符串进阶算法 1 ：exKMP、SA、SAM、后缀平衡树
字符串进阶算法 1 ：exKMP、SA、SAM、后缀平衡树 exKMP / Z函数 对于字符串 sss 的每个后缀，求其与 sss 的最长公共前缀 ziz_izi 要求 O(n)O(n)O(n) 我们考虑当前在对 iii 进行操作。 之前已经有一段区间 [l,r][l,r][l,r] 满足 s[1,r−l+1]=s[l,r]s[1,r-l+1]=s[l, r]s[1,r−l+1]=s[l,r]，且 rrr 最大。 若 i≤ri\le ri≤r，则直接继承 zi=zi−l+1z_i=z_{i - l + 1}zi=zi−l+1 接下来暴力匹配，只要匹配成功，此时 rrr...
2022-01-08
【ZR #540. 【19普转提4】串串】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15778576.html 题目链接 题目 给定两个长度为 nnn 的只包含’a’,‘b’,'c’的字符串s,ts,ts,t。 请打乱串 sss，使得 ∀i,si≠ti\forall i,s_i \not= t_i∀i,si=ti，且 sss 字典序最小。 思路 对于 ttt 串中从前往后每一个字母，在 sss 的剩余可选字母中选字典序最小的。 如果 sss 的剩余字母中没了，就往前找第一个可以替换的替换。 最后再对每种 ttt 中的字母按...