[后缀自动机]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】题解
题目概述给定一个字符串 $S$ ，要求构造字符串序列 $s_1, s_2, \ldots, s_k$ ，满足任意 $s_i$ 都是 $S$ 的子串，且任意 $i \in$ $[2, n]$ ，都...
