ZigZagK的博客
[后缀数组+复杂度分析]2022牛客暑期多校训练营7 I【Suffix Sort】题解
题目概述Suffix Sort解题报告一直在想Hash,然后寄了……实际上应该分析一下性质。首先有一个比较显然的想法是将 $S$ 变为另一个数组,$a_i$ 表示 $S_i$ 与上一个相同字符的...
[KMP+后缀数组+主席树]2022牛客暑期多校训练营6 L【Striking String Problem】题解
题目概述Striking String Problem解题报告神仙题,根本想不到。记 $n$ 为 $S$ 长度,$m$ 为 $T$ 长度,$U_i$ 表示 $S[l_1,r_1]+\cdots+...
[后缀自动机]The 2021 ICPC Asia Shenyang Regional Contest M【String Problem】题解
题目概述String Problem解题报告首先很显然,对于前缀 $i$ ,答案一定是某一个位置到 $i$ 。用后缀数组可以做,但是思考起来比较麻烦。考虑后缀自动机,在建立后缀自动机的时候我们记...
[后缀数组+离线+扫描线+线段树二分]2021 CCPC 桂林 J【Suffix Automaton】题解
题目概述Suffix Automaton解题报告被时限骗了,以为做法是两个 $\log$(空间爆炸),其实只要离线就可以一个 $\log$ 。求出后缀数组后,第 $i$ 个后缀多出来的就是 $[...
[二分+后缀数组]HDU2328【Corporate Identity】题解
题目概述HDU2328解题报告首先将所有串中间隔开接起来(注意中间隔开的字符不能相同)。二分枚举答案 $len$ ,然后根据 $Height$ 数组分块,每个块中检查是否 $n$ 个字符串都出现...
[后缀数组]HDU3518【Boring counting】题解
题目概述HDU3518解题报告枚举子串的长度 $len$ ,然后将后缀数组按照 $Height\ge len$ 分块,每个块中检查最左和最右的子串是否交叉就行了。示例程序#include<...
[离线+后缀数组+STL乱搞]LOJ6041(雅礼集训 2017 Day7)【事情的相似度】题解
题目概述有长度为 $n$ 的 $01$ 串 $s$ 和 $m$ 个询问,每次询问 $[L,R]$ 表示 $s$ 的 $[L,R]$ 这些前缀之间的最大公共后缀。解题报告SAM+LCT什么的好大啊...
[后缀数组+线段树]LOJ2064(HAOI2016)【找相同字符】题解
题目概述给定两个字符串,求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。解题报告先套路一波:把两个串接在一起(加个分隔符),求后缀数组...
[二分+后缀数组]BZOJ4310【跳蚤】题解
题目概述有一个串 $S$ ,现在要把 $S$ 分成不超过 $k$ 段,从每一个子串选出最大的子串,再从这些最大的子串中选出最大的串"JZ串",求最小的"JZ串"(题面有误,应该是最小的而不是最大...