ZigZagK的博客
[后缀自动机parent树+虚树]2022牛客暑期多校训练营1 B【Spirit Circle Observation】题解
题目概述Spirit Circle Observation解题报告找性质题最烦了.jpg。首先建SAM,考虑一个直观的做法。直接考虑枚举SAM里的节点,然后在节点上考虑 $a999\cdots$...
[后缀自动机+拓扑]LOJ3049【「十二省联考 2019」字符串问题】题解
题目概述LOJ3049解题报告把串反过来,那么 $B$ 是 $A$ 前缀就变成 $B$ 是 $A$ 后缀,也就是 $B$ 是 $A$ 在SAM上的parent树祖先,或者B和A在SAM同一个节点...
[广义后缀自动机]2021 ICPC 澳门 I【LCS Spanning Tree】题解
题目概述LCS Spanning Tree解题报告听说这题卡倍增SA,表示强烈谴责😡(不过我没想到SA怎么做)。由于需要求任意两个字符串之间的最长公共子串,因此考虑广义SAM,在构造时,记录一下...
[后缀自动机]The 2021 ICPC Asia Shenyang Regional Contest M【String Problem】题解
题目概述String Problem解题报告首先很显然,对于前缀 $i$ ,答案一定是某一个位置到 $i$ 。用后缀数组可以做,但是思考起来比较麻烦。考虑后缀自动机,在建立后缀自动机的时候我们记...
[广义后缀自动机+二分]2021-2022 ACM-ICPC Brazil Subregional Programming Contest B【Beautiful Words】题解
题目概述Beautiful Words解题报告先把 $A$ 复制一份,令 $B_i=A[i-n+1,i]$ 。然后二分答案 $mid$ ,这样就只需要验证是否存在 $i\in[n,2n-1]$ ...
[广义SAM]BZOJ3926(Zjoi2015)【诸神眷顾的幻想乡】题解
题目概述有一棵 $n$ 个节点的树,每个节点有一个字符。定义一条路径 $(x,y)$ 形成的字符串为从 $x$ 走到 $y$ 路径上所有字符按顺序接起来形成的字符串。求所有本质不同的字符串。叶子...
[贪心+后缀自动机+线段树合并]Codeforces700E【Cool Slogans】题解
题目概述有一个串,现在要找出这个串的一个子串使得这个子串在原串出现了至少 $2$ 次,接着对这个子串继续操作直到无法操作为止。求最多操作多少次。解题报告Div.1好难啊……因为要求最大值,所以贪...