CF666E Forensic Examination
Codeforces Luogu 分析 先对 $T_{1..m}$ 建立广义 SAM，然后把 $S$ 丢上去匹配，记录每个前缀匹配到的节点 $pos_i$。 考虑对每个节点维护一棵以 $T$ 的下标为下标的线段树，线段树上的每个节点维护当前串在这些 $T$ 串中的出现次数的最大值及其下标。这可以通过线段树合并预处理出来。 询问时，我们首先找到 $s_{l..r}$ 所在的节点，直接从 $po...
Codeforces Luogu 分析 先对 $T_{1..m}$ 建立广义 SAM，然后把 $S$ 丢上去匹配，记录每个前缀匹配到的节点 $pos_i$。 考虑对每个节点维护一棵以 $T$ 的下标为下标的线段树，线段树上的每个节点维护当前串在这些 $T$ 串中的出现次数的最大值及其下标。这可以通过线段树合并预处理出来。 询问时，我们首先找到 $s_{l..r}$ 所在的节点，直接从 $po...
Luogu LOJ 分析 首先容斥一下，求出三段都不包含 $s_{l..r}$ 的方案数，然后用 ${n-1\choose 2}$ 减掉即为答案。 我们先把所有和 $s_{l..r}$ 相等的子串位置都找到，然后分类讨论一下： 如果有三个互不相交的串，方案数是 $0$。 如果最左边的串和最右边的串相交： 考虑 $i$ 的位置： 如果 $i\in[1,l_1)$，那么 $j\in(l_m,...
Luogu LOJ 分析 容易想到一个图论模型，即从每个 A 类串向它所支配的 B 类串连边，从每个 B 类串向以它为前缀的 A 类串连边，并将所有 A 类串的权值设为长度。这样问题变为求最长路，如果有环输出 -1。 第一类边可以直接连，但第二类边暴力连显然不行，考虑一些优化。 对反串建 SAM，此时 Parent 树上每个点的祖先都是它的前缀，于是我们只需要将树上每个 B 类串对应的节点向...
SPOJ Luogu 分析 首先思路肯定就是建 SAM，询问就找到对应位置然后求 $size$。 然而我们要支持插入，也就是要动态维护 $size$。 可以用 LCT 维护 Parent 树，每次相当于求子树和，用维护子树信息那一套即可。当然也可以直接链修改。 代码 我的写法可能有点奇怪 /kel // ==================================== // au...
Luogu LOJ 分析 先考虑 $l=1,r=|S|$ 的情况。 对 $S$ 和 $T$ 建 SAM。 设 $lim_i$ 表示 $T[1..i]$ 最长的是 $S$ 的子串的后缀的长度，可以在 $S$ 的 SAM 的 Parent 树上跳来求出： 如果有对应的转移直接走过去，匹配长度加 $1$； 否则跳 Parent 树，直到某个点有对应的转移，匹配长度变为该点的 $len$； 如果跳...
Codeforces Luogu 分析 为了方便，把串翻转，条件改为「使 $t_{i-1}$ 是 $t_i$ 的真子串」。 可以发现一个性质，即在一定存在一组最优解使得 $|t_i|=i$，因为某个不满足的串删去多的部分一定不会差。 于是可以考虑一个 DP。设 $dp_i$ 表示最后一个串以 $i$ 结尾时最多能选出多少个串。 然而这个似乎没法转移。冷静分析一下可以发现一定有 $dp_{i-...