Sam做题记录

时间:2023-01-09 22:13:30

Sam做题记录

Hihocoder 后缀自动机二·重复旋律5

求一个串中本质不同的子串数

显然,答案是 \(\sum len[i]-len[fa[i]]\)

Hihocoder 后缀自动机三·重复旋律6

求一个串每个长度出现次数的最大值

求出fail树每个点的size就是该点的出现次数,由于答案是(非严格)单调减的,每个点更新一下 \(ans[len[i]]\)

Hihocoder 后缀自动机四·重复旋律7

求几个数字串本质不同的子串所代表的数的和, \(mod\ 10^9+7\)

先建一下广义sam,在转移边上bfs更新答案

Hihocoder 后缀自动机五·重复旋律8

给定一个字符串S,询问另一个字符串T的子串和S的子串匹配数。匹配的定义为两个串循环同构。

对S建Sam,把T倍长之后在Sam上跑,如果一个位置匹配长度大于|T|,那么沿着fail树向上跳到 \(len[i]>=|T|\) 的最小的 \(len[i]\) ,如果没有被更新过那么更新答案

[USACO17DEC] Standing Out from the Herd

给定多个字符串,求每个字符串只属于他自己的本质不同的子串数

建广义Sam,如果一个状态他在多个字符串中出现,那么他没有贡献,否则给他所在的字符串贡献 \(len[i]-len[fa[i]]\)

「20180714NOI模拟」Ernd

给定一个长度为 \(n\) 且仅包含小写英文字母的字符串 \(S\)。你有一个字符串 \(T\),初始为空串。

你可以进行 \(n\) 次操作,每次操作你可以在 \(T\) 的前端或末尾加入一个任意字母。记第 \(i\) 次操作后 \(T\) 在 \(S\) 中的出现次数为 \(f_i\),你需要最大化 \(ans =\sum_{i}^{} f_i\)。

对S建Sam,在末尾加入字母就是沿着匹配边走,在前面加字母就是在fail树往下走,直接把这些边全连上跑拓扑就行了

[ZJOI2015]诸神眷顾的幻想乡

给定一棵无根树,每个点有一个字符,求本质不同的子串数,叶子节点不超过20个

注意到最后那个条件,直接每个叶子拎出来,插到sam里,然后同第一题

BZOJ2894 世界线

给定一棵Trie,求不同子串数和第K小子串

建广义Sam,第一问不说了,第二问先求出每个点沿着转移边能走多少条路,然后按位贪心

[HEOI2015]最短不公共子串

给两个小写字母串A,B,请你计算:

(1) A的一个最短的子串,它不是B的子串

(2) A的一个最短的子串,它不是B的子序列

(3) A的一个最短的子序列,它不是B的子串

(4) A的一个最短的子序列,它不是B的子序列

建Sam和序列自动机(就是求出 \(next[i][c]\) 数组, 表示第 \(i\) 个位置下一个字符 \(c\) 的位置)

然后几个询问都是在某两个自动机上跑BFS

[Feyat cup 1.5]Str

求两个字符串的最长公共字串,两个字符串相等的条件是它们至多有一个位置不同

考虑暴力:枚举两个字符串不同的位置 \(i, j\) ,那么答案为 \(lcs(a_{1\dots i - 1},b_{1\dots j -1}) + 1 + lcp(a_{i + 1 \dots |a|},b_{j+1\dots|b|})\)

假设我们知道 \(i, j\) ,那么这个值可以在 SAM 或者 SA 上查出来 (把两个串连一下,正反各建一个即可)

考虑优化这个枚举的过程

根据 SA,如果我们知道如果 \(i, j\) 的 \(rank\) 越接近,那么它的 LCP 就越大,那么可以想到用set维护一下这个东西

LCS是什么东西?两个点在 SAM 上的对应节点的在 $ parent $ 树上的 LCA 的 \(len\) 就是它们的 LCS!

因此,在 \(parent\) 树上启发式合并,然后像启发式那样去查就行了

复杂度 \(O(nlog^2n)\) 好像可以一个 \(log\) 不过我还暂时不会。。

[HAOI2016]找相同字符

给定两个字符串,求出在两个字符串中各取出一个子串使得这两个子串相同的方案数

就两个串,建一下广义 SAM ,然后对每个串记录一下每个节点的 \(size\) 乘一下加起来即可

[HEOI2016/TJOI2016]字符串

给定字符串 \(S\) ,多次询问子串s[a..b]的所有子串和s[c..d]的最长公共前缀的长度的最大值

首先反着建 SAM,\(lcp\) 就转化为 \(lcs\) ,二分答案 \(ans\),然后就转化为问 \(endpos\) 为 \(c\) 的 \(len \ge ans\) 的节点的 \(endpos\) 集合中是否包含 \(a\dots b - ans+1\) 的某个值,线段树合并求 \(endpos\) 然后查一下就行了。注意每次询问还要找到最小的 \(len \ge ans\) 的节点,在 \(parent\) 树上倍增即可

[CTSC2012]熟悉的文章

给一堆01模板串,然后询问把一个另外的串 \(S\) 分割成若干段,长度大于等于 \(L\) 的且在模板串里出现过的子串长度总和不小于 \(|S|\) ,求最大的 \(L\)

建广义 \(SAM\), 把询问串放在上面匹配,可以求出每个位置结尾的最大匹配长度,然后二分一个答案,然后单调队列优化一下DP

具体地,\(f[i]\) 表示已经决策到 \(i\) ,目前的最大长度
\[
f[i]=\max_{i-j\le ans}f[j]+i-j
\]

CC Killjee and k-th letter

给你一个字符串 \(S\),定义它的生成串 \(T\) 为 \(S\) 的所有子串(位置不同算多个)按照字典序排序后,依次串接形成的串,多次询问 \(T_i\)

建出后缀树,你发现后缀树就是个 Trie,每条路径都可以代表一个子串,按照出边排序一下,就可以发现 直接在这个 Trie 上 DFS就可以得到正确的顺序,所以按照 DFS 序处理一下,搞个前缀和,查询的时候计算计算即可

[NOI2015]品酒大会

给定一个串 \(S\) 和序列 \(a\) ,对于所有 \(r\) 求 \(\max_{i\neq j,lcp(suf_i,suf_j)\ge r} a_i\times a_j\)

反着建SAM,然后直接在上面合并,记录一下子树 \(min_a,max_a\) 因为这个 \(a\) 可以是负数

[NOI2016]优秀的拆分

求字符串 \(S\) 中所有形如 \(AABB\) 的字串个数

神仙题

显然就是求 每个点 左右的 \(AA\) 个数 乘起来求和

咋求这个?hash暴力求可以95

100分:枚举一个长度 \(T\) ,然后每隔 \(T\) 个字符设置一个关键点,求出每两个相邻关键点的 \(lcp,lcs\) ,

显然,左边 的 \(lcp\) 和右边的 \(lcs\) 是这个字串的一个 \(border\)

如果 \(lcp+lcs<T\) ,那么不会出现循环,就没有 \(A\) 出现,否则 就会出现循环的情况,限制一下 \(lcp,lcs\) 都不能超过 \(T\),那么那个循环就不会超过两次,即出现了 \(AA\) 用前缀和优化一下

复杂度 \(O(n\ln n)\)

CF666E Forensic Examination

给你一个串 \(S\) 以及一个字符串数组 \(T[1..m]\),\(q\)次询问,每次问\(S\)的子串\(S[p_l..p_r]\)在\(T[l..r]\)中的哪个串里的出现次数最多,并输出出现次数。

如有多解输出最靠前的那一个。

对 \(T\) 建广义SAM,然后 \(S\) 在上面跑,求出 \(S\) 每个位置对应节点,询问的时候,倍增的往上跳到\(S[p_l..p_r]\) 对应节点,然后查询一下(可以线段树合并预处理)

[CTSC2010]珠宝商

给你一棵字符树,和一个串 \(S\),求每个路径代表串在 \(S\) 中出现次数之和

路径问题,考虑点分治。

对于每个分治中心,需要求出经过他的路径的答案。

如果知道了以这个分治中心为前缀和后缀的在 \(S\) 的每个位置的出现次数,那么对应乘起来就是总次数了

那么对 \(S\) 的正反串分别建SAM,然后在SAM上跑就可以分别求出这两个值,那么怎么求出每个位置对应的值呢

考虑自底向上求 \(endpos\) 集合的过程,只要把这个过程倒过来,往下推,就可以了

每次这样搞,复杂度 \(O(|S|)\) ,显然在子树很小的时候不优,所以在子树小于 \(\sqrt{|S|}\) 的时候,直接dfs搜出每条路径然后在 \(S\) 的SAM上跑即可。