[思维+后缀数组+调和级数]LOJ2083【「NOI2016」优秀的拆分】题解
题目概述LOJ2083解题报告想了很久匹配做法，不会做，实际上是性质题……如果能求出 $pre_i$ 表示以 $i$ 结尾的 $AA$ 个数和 $suf_i$ 表示以 $i$ 开头的 $BB$ ...
[后缀自动机+线段树合并+后缀数组]LOJ2720【「NOI2018」你的名字】题解
题目概述LOJ2720解题报告毒瘤字符串题……这题的关键在于，给出串 $T$ ，在 $S$ 的 $[L,R]$ 子串中查询每个后缀的最长匹配前缀。倒着考虑 $T$ 的每个后缀 $i$ ，求出在 ...
[后缀数组+复杂度分析]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)【找相同字符】题解
题目概述给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。解题报告先套路一波：把两个串接在一起（加个分隔符），求后缀数组...
