[题解] [Alpha1022 的无趣比赛] 光棱碎片

[题解] [Alpha1022 的无趣比赛] 光棱碎片

给定字符串 $S$,每一位额外有权值 $v_i$,求有多少对 无序的 本质相同但出现位置不同的子串(右端点分别为 $r_1,r_2$)满足 $L\le (v_{r_1}\oplus v_{r_2})+len\le R$,其中 $L$、$R$ 为给定参数。答案对 $998244353$ 取模。

$1\le |S|,v_i,L,R\le 10^5$

阅读更多
[题解] [TJOI2013] 单词

[题解] [TJOI2013] 单词

一篇论文是由许多单词组成,但小张发现一个单词会在论文中出现很多次,问每个单词分别在论文中出现了多少次。

$1\le n \le 200$,单词总长度不超过 $10^6$

阅读更多
关于广义后缀自动机

关于广义后缀自动机

约束

tar[x][c]:SAM 转移

pre[x]:常用名有 linkfail(反正就那个东西)

len[x]:结点 x 代表的最长字符串的长度


广义后缀自动机(下文用广义 SAM 指代),即用多个字符串的后缀建出的一个后缀自动机,拥有和后缀自动机相似的性质。

有三种较流传广泛的广义后缀自动机写法:

阅读更多