SAM字符串题目选做

~~这类题好多也可以用后缀数组和后缀平衡树, 但我还是热爱SAM. ~~

一开始是SAM题目选做, 现在也会加入部分其他字符串.

P4022 熟悉的文章 [SAM] [dp]

给定01串标准文章, 定义一个01串是熟悉的当且仅当长度大于 $L$ 且z在标准文章中出现过. 现 $q$ 次给定询问串 $T$ , 求最大的 $L$ 使得可以把 $T$ 分成若干段, 其中有90%以上是熟悉的.

输入文件小于1100000Byte.

对于一篇作文, 可以求出每个点向前最多匹配多长还在标准作文库中(zsy数组), 这里前是指向下标小的方向(似乎对于序列, 前和后会产生歧义) 把这个长度记为 $len_i$ , 方法:

  • 建出包含所有作文库作文的SAM.

  • 初始匹配长度为0, p 借点在根, 每次若能匹配沿自动机边向前走, 否则跳parent tree, 注意向前匹配时匹配长度不能直接用 p 点 sam 节点的len值, 但跳parent tree树时可以.

-qyc: 这里暴力跳parent tree是对的因为跳一步深度减一, 匹配一个深度加一, 所以总复杂度O(n)

然后考虑二分答案, 对于每一个答案, 进行判断, 方法:

  • $f_i$ 表示 考虑前 i 位时, 最多能有多少位是熟悉的, 转移就是考虑前面匹配到哪里 $f_i = \max_j {f_j + i - j }, s. t. \ j \in [i-len_i, i-l]$ .

  • 这样做是 $O(n^2)$ 的, 发现可以进行简单单调队列优化, 总复杂度 $O(n\log n)$

  • 最后判断熟悉的位数是否多于90%.

P6640 封印 [SAM] [二分答案]

给出只包含小写字母 $a, b$ 的两个字符串 $s, t$ , $q$ 次询问, 每次询问 $s[l \dots r]$ 和 $t$ 的最长公共子串长度.

$\vert s \vert , \vert t \vert \le 2\times 10^5, q\le 2\times 10^5$

向熟悉的文章一样, 可以先求出s中每个点向前匹配多长还在t中, 二分答案, 若当前答案为x, 询问为 l, r , 则只要判断 $\min {len[l+x-1, r]}$ 这段区间的最大值是否不小于x即可, 于是你需要一个静态RMQ, 为了不写成2log, 于是学了猫树.

猫树要注意:

  • 补成完全二叉树时(即要把 $n$ 弄成2的倍数)才满足叶子lca为叶子编号的lcp.

  • 只要求出lca在第几层, 设编号为x和y, 则层数为 $\lg{x}-\lg{x \mathrm {xor} y}$ .

P4094 字符串 [SAM] [线段树合并] [二分答案]

给定字符串 $s$ , $q$ 次询问区间 $[a, b]$ 中的所有子串与 $[c, d]$ 的最长公共前缀长度.
$\vert s \vert , q\le 2\times 10^5$

二分答案, 对于一个答案x, 从s[1. . d]跳parent tree到最后一个长度大于x的节点, 看这个节点的endpos是否有在[a+len-1, b]之间的, 所以用线段树合并维护endpos, 复杂度 $O(n\log^2n)$

P4770 NOI2018 你的名字 [SAM] [线段树合并] [区间SAM]

给一个串 $S$ , $q$ 次询问在 $T$ 中但不在串 $S$ 的区间 $[l, r]$ 中的本质不同子串个数. $\vert S \vert \le 5\times 10^5, \sum \vert T \vert \le 10^6$ .

首先考虑询问 $S$ 整串与 $T$ 的答案的情况, 此时可以对 $S$ 和 $T$ 建SAM. 同时容易想到容斥成在 $T$ 的本质不同子串数减去同时在 $S$ 和 $T$ 中出现的本质不同子串数.

同时出现的子串数有经典做法广义SAM, 但因为多次询问死了, 要让复杂度关于 $\vert T \vert$ 而不是 $\vert S \vert$ .

考虑拓展本质不同子串数的办法, 我们求和了所有 $T$ 的SAM节点代表的子串个数 $len-father. len$ , 那么求和 $\min(lim, len)-father. len$ 就是共同出现的, 其中 $lim$ 表示这个节点代表的子串中所有在 $S$ 中的长度最大值 . 然后你发现根本不用容斥, 直接求和 $\max(0, len-\max(father. len, lim))$ 就行了. 能想到这个 $lim$ 大概是因为它和封印, 熟悉的文章的zsy数组类似. 那么考虑求 $lim$ , zsy数组求法是成熟的, 由于对于一个点表示的所有串情况是相同的, 所以 $lim$ 可以取第一次出现位置的zsy数组值.

这样做复杂度就只根 $\vert T \vert$ 相关了. 复杂度 $\vert S \vert +\sum \vert T \vert$ 考虑如何再拓展到区间上.

考虑我们对于 $S$ 的SAM要支持在区间意义下:

  • 跳parent tree

  • 查转移边

  • 查 $len$

于是思考SAM的节点定义, 压缩的是全串信息的情况下, 一定保留了区间的所有信息, 唯一不同是可能压缩不彻底. 于是想到利用全局的SAM实现区间信息:

  • parent tree可以直接用全局的, 因为在全局上的父亲一定是区间上的祖先, 区别仅在于在区间意义下endpos从真包含变成可能相等.

  • 转移边也可以用全局的, 但有可能转移到的其实在外面, 要判断转移到的是否在区间里.

  • $len$ 也可以用全局的, 但有可能这个节点代表的最长串延伸出区间.

而线段树合并维护 $endpos$ 是众所周知的, 于是实现就是, 在S的SAM上线段树合并, 然后我们代码类似于:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
p = s_sam.root;
int len = 0;
for (int i = 1; i <= m; i++) {
    while (true) {
        if (s_sam.ns[p].nxt[t[i]] && segs[roots[s_sam.ns[p].nxt[t[i]]]].query(1, n, sl + len, sr)) {
            len++;
            p = s_sam.ns[p].nxt[t[i]];
            break;
        }
        if (!len)
            break;
        len--;
        if (len == s_sam.ns[s_sam.ns[p].link].len)
            p = s_sam.ns[p].link;
    }
    lens[i] = len;
}

要点: 有可能一个节点最长的子串在区间外而较短的在区间内, 而我们线段树判断 $endpos$ 的时候需要长度作为参数, 所以当不匹配时要把已经匹配的长度一个一个一个变短, 直到长度变成父亲的长度再跳parent tree而不能直接跳.

最后就冲代码吧. 建议把SAM封装一下 $S$ 和 $T$ 可以共用. 然后线段树合并的时候可以只在非叶子且儿子都不为空的情况下新建节点.

CF119D String Transformation [exkmp]

给两个字符串 $a, b$ , 定义 $r(s)$ 表示串 $s$ 的逆序串, 求 $i, j$ 使得 $a_{i+1\ldots j-1}+r(a_{j\ldots \vert s \vert})+r(a_{1\ldots i})=b$
$\vert a\vert, \vert b\vert \le 10^6, \vert \sigma\vert \le 94$

不会Z函数, 死了死了. 哦实际上是个简单题啊.

就是你确定了 $i$ 之后, 变成了切成两段, 然后判断是否能匹配, 就是求 $a, b$ 两个前/后缀的匹配长度, 用z函数处理然后直接判断.

CF123D String [SAM]

给出字符串 $s$ , 定义子串 $a$ 在 $s$ 中的出现次数为 $cnt(a)$ , 求 $\sum \frac{cnt(a)(cnt(a)+1)}{2}$ .
$\vert s\vert \le 10^5$

直接SAM

CF235C Cyclical Quest [SAM]

给定一个主串 $s$ 和 $n$ 个询问串, 求每个询问串的所有循环同构在主串中出现的次数总和.

$n\le 10^5$ , $\vert s \vert \le 10^6$

如果一个题是 SAM, 但不是直接 SAM, 那就是在 SAM 上跑匹配

考虑把一个询问串 $t$ 的复制一倍在 SAM 上跑匹配, 那么如果当前匹配长度大于 $\vert t \vert$ , 就可以加上这个SAM上节点的出现次数.

然后一个问题是可能 $t$ 的不同循环同构可能相等, 那么一个方法是用 KMP 跑出它的周期, 另一个做法是直接在 SAM 上经过的节点打标记, 就结束了

记录广义SAM的特判

好像已经广为人知了, 我比较致远星.

本来写法是直接每次插入一个串之后 $last$ 指向 $root$ .

rewrite 2024. 3. 1

出现问题的情况是, 我们要插入一个字符时 $last已经有对应字符的出边:

  • 如果出边指向的等价类长度和$ last $长度差$ 1 $, 那么它就是我们要建的点, 此时返回它即可.
  • 如果出边指向的等价类长度不对, 那么应该把它分裂.

而离线建法中, 容易发现bfs保证了不会有出边(没有插入过包含当前前缀的字符), dfs保证了不会有长度差$ 1 $的出边.

P7114 [NOIP2020] 字符串匹配

复习KMP, 发现这个题还没补.

给定$ s $, 求把$ s $划分成$(ab)\cdot x+c, x\ge 1 $的方案数, 定义乘法是重复若干次, 加法是拼接, 并要求$ a $中出现奇数次的字符数少于$ c $.

$ n\le 2^{20} $

看起来最性质的当然是$ s=ab $, 枚举它, 再调和级数的枚举个$ i $, 也就确定了$ c $, 问题就成了前$ i $个前缀有多少个出现奇数次字符少于$ c $的, 需要$ O(1)$, 考虑$ s $是从前往后, 每往后一位暴力改前缀和, 复杂度$ 26n+n\ln n $, 哈希被卡常了(取模), kmp还是没问题的.

本机比luogu慢了一倍.

P2444 [POI2000] 病毒

建出一张图, 节点表示状态, 边表示走字符$ 0/1 $到达哪个点, 至于状态是什么可以直接上AC自动机, 其中的点就是状态.

用SAM真是愚蠢的决定, 因为标记合法状态是困难的.