ResurrectionTX

题解

比赛(7) 笔记(6)

/ 注册

全部文章 / 题解（共6篇）

Codeforces 235C 【Cyclical Quest】

Description 传送门 Solution 考虑循环同构的性质，每次相当于从最前面删去一个字符，从最后面加上一个字符。在\(SAM\)里对应着往上跳\(fa\)或不跳和走对应的字符串转移边。考虑对于长度为\(l\)的串，最多删\(l\)次，最多加\(l\)次，所以直接在\(SAM...

SAM 字符串 Codeforces

2020-06-12

0 530

Luogu P5840 【[COCI2015]Divljak】

Description 传送门 Solution 首先看到这题就想SAM对吧，然后qwaszx写了一发常数太大过不了就果断改AC自动机对吧。考虑对\(S\)建立\(AC\)自动机，因为字符串的所有前缀的所有后缀是字符串的所有子串，而\(fail\)指针指的状态就是该状态的最长可识别后缀...

AC自动机字符串 Luogu

2020-06-12

0 435

BZOJ 4502 串

Description 传送门 Solution 首先注意到很多字符串有很多不同的方式进行划分，这样子为了避免不重不漏，就需要对其按特定形式划分。考虑到\(AC\)自动机上\(fail\)指针的含义是状态\(x\)的最长可识别后缀，那么我们就把划分方式定义为使划分的后半部分子串最长即可。 ...

BZOJ 字符串 AC自动机

2020-06-12

0 374

Luogu P3181 【[HAOI2016]找相同字符】

Description 传送门 Solution 这题就是让求两个串的相同子串的个数。众所周知，字符串所有的子串就是字符串所有的后缀的所有前缀。利用这个性质我们可以将问题转化，变成求两个字符串的所有后缀的\(lcp\)的长度的和。求后缀的\(lcp\)我们可以使用\(SA\)。...

单调栈 SA 字符串 Luogu

2020-06-12

0 374

BZOJ 3145 Str

Description 传送门 Solution 如果直接暴力的话，可以枚举那个不同的字符在串一和串二里的位置分别是什么，然后算一下他们的\(lcp\)和\(lcs\)来更新答案，也就是\(\sum_{i = 1, j = 1} ^{i <= n, j <= m} lcp(i ...

启发式合并字符串 SA BZOJ

2020-06-15

0 397

Luogu P5212 【SubString】

Description 传送门 Solution 动态加入字符就用\(SAM\)，发现答案就是一个点的子树的\(siz\)之和，所以需要动态维护子树和，上\(LCT\)。 \(lCT\)上每个节点，\(siz\)表示\(Splay\)上大小，\(lsiz\)表示虚子树大小，修改\(Upd...

Link-Cut-Tree 字符串 SAM Luogu

2020-06-16

0 381