P6292 区间本质不同子串个数

给定字符串，多次询问区间本质不同子串数

类似区间数颜色，将询问离线之后，移动右端点，维护左端点的答案，每次修改access一下，是一个区间加区间求和。

P5576 [CmdOI2019]口头禅

给定一堆字符串，多次询问区间字符串最长公共子串。

广义SAM，用set维护子树内有的连续区间，自底向上启发式合并，增加区间时在线段树上查找可以回答的询问，并且将该询问删除。由于自底向上，保证len越来越小，所以回答完就可以删除。

P4482 [BJWC2018]Border 的四种求法

多次询问字符串区间border。

parent树上链分治。

先考虑 \(node_r\) 暴力向上跳，找 pos 集合区间最大值的方法。HLD 之后把跳的过程拆到重链上。利用轻子树大小和为 \(O(n\log n)\)，每条重链处理，要求 \(pos-len < L\)，线段树以 \(pos\) 为下标，维护 \(\min\{pos-len\}\)，然后线段树上二分。

CF1098F Ж-function

多次询问 \(f(l, r)\) 表示子串 \(s[l, r]\) 每个后缀与该子串的 lcp 的和。

思路同上，用 HLD 优化暴力跳的过程，拆到重链上变成一个三维偏序，然后用 CDQ 分治做。

2022牛客多校6 L Striking String Problem

给定串 \(S, T\)，令 \(U = S[l_1, r_1] + S[l_2, r_2] + \dots + S[l_k, r_k]\)，\(q\) 次询问 \(T\) 在 \(U[x_i, y_i]\) 中的出现次数。

数据结构优化KMP。

询问可以拆成两个前缀的答案之差，考虑对一个前缀的查询，设它在 \(S[l_i, r_i]\) 里，预处理前 \(i-1\) 的答案，设 \(\operatorname{query}(i, p)\) 表示右端点在 \([l_i, l_i+p)\) 的答案，完全落在 \(S[l, r]\) 内的答案可以预处理前缀和。

跨过 \(l_i\) 的答案，设超出长度为 \(D\)，需要满足 \(D+p \geq |T|, D+\operatorname{lcp}(S[l:], T[D+1:]) \geq |T|\)，对于同一个 \(D\)，\(S[l:]\) 要满足的条件是后缀树上的一个子树。

对 \(T\) 的 kmp 失配树建可持久化线段树，区间修改单点查询。满足条件的 \(D\) 是失配树上的一个祖孙链，需要知道 \(S[l_1, r_1]+\dots+S[l_{i-1}, r_{i-1}]\) 和 \(T\) 的匹配长度，这个可以预处理，分匹配完全在 \(S[l, r]\) 和跨左端点讨论一下，后者还是在失配树上用线段树搞一下。

CF700E Cool Slogans

给定字符串 \(S\)，求字符串序列 \(s_1, s_2, \dots, s_k\) 的最大长度，满足 \(s_i\) 是 \(S\) 的子串，并且 \(s_{i-1}\) 在 \(s_i\) 中出现至少两次。

关键思路是，转换成前一个串是后一个串的 border。

然后在 parent 树上从上往下 dp，dp值加1的条件是dp值为当前值的最短串在当前串中出现了2次，用线段树合并维护endpos集合即可。

CF1063F String Journey

给定字符串 \(S\)，从 \(S\) 中按顺序拿出一些不相交的子串，使得前一个串是后一个串的真子串，求最多的数量。

观察1：存在答案，len是1,2,3…，在这个前提下，设 \(dp_i\) 表示存在以 \(i\) 结尾的长度为 \(dp_i\) 的序列；

观察2: dp(i) <= dp(i-1)+1，这是由于将 \(dp_{i+1}\) 那个方案中每个字符串末尾去掉一个字符可以构造出一个 \(dp_i\) 的方案。于是可以每次从 \(dp_{i-1}+1\) 倒着枚举并且用倍增+线段树 check 一个区间是否存在某个位置 dp >= k，显然是 \(O(n\log n)\) 的。

P6095 [JSOI2015]串分割

给定只包含 \(1\cdots 9\) 的数字环状串，要求切成 \(k\) 段字符串，使得十进制表示下最大的数字最小。输出这个值。

显然答案串长为 \(v = \lceil \frac{n}{k} \rceil\)，先求后缀数组，然后二分答案串的排名。断环成链，枚举 \(v\) 个断点，每次能取 \(v\) 就取 \(v\)，不然就取 \(v-1\)，显然这样就是对的。

ICPC2021 沈阳 M String Problem

给定字符串 \(S\)，求每个前缀的字典序最大的子串。

昨晚有人问我这题怎么做，回来详细说一下当时的做法。

显然一个字符串最大的子串是它的一个后缀，用起始位置 \(l\) 表示，为了比较后缀大小，建出后缀数组，用排名 \(rank_l\) 来表示后缀 \(l\) 的大小。

显然只有前缀最大值能成为答案，而且答案的左端点是单调不降的。考虑用队列维护当前的前缀最大值，队首是当前的答案，如果队首比下一个小的话就弹掉。

这样可能会存在一个疑问，是否可能出现 \(l_1, l_2, l_3\) 满足 \([l_2, i]\) 是 \([l_1, i]\) 的前缀，此时不会弹掉 \(l_1\)，但是 \([l_3, i]\) 更大，但是如果出现这种情况，由于 \([l_2, i]\) 包含了 \([l_3, i]\)，后者必然在之前就出现过，\(l_2\) 必不可能成为前缀最大值。

Duff is Mad

给定 \(n\) 个字符串 \(s_{1 \dots n}\)。

\(q\) 次询问 \(s_{l \dots r}\) 在 \(s_k\) 中出现了多少次。

\(n,q,\sum_{i=1}^n |s_i| \le 10^5\)。

出现多串一定要考虑一下根号分治。

对于 \(|s_k| < B\) 的，可以在 ac 自动机上暴力跑，差分一下用扫描线求一下，需要一个 \(O(\sqrt N)\) - \(O(1)\) 的数据结构。

对于 \(|s_k| \geq B\) 的，这样的串不会有很多种，对于每种，把该串在ac自动机上的路径加1，然后计算子树和就可获得每个点在该串的出现次数。

总复杂度 \(O(n\sqrt n)\)

P8571 [JRKSJ R6] Dedicatus545

对于字符串 \(x,y\)，定义 \(w(x,y)\) 为 \(x\) 在 \(y\) 中的出现次数。

Index 给了你 \(n\) 个字符串 \(s_{1\dots n}\)，\(m\) 次询问，每次询问给定 \(l,r,k\)，求 \(\max_{i=l}^r w(s_i,s_k)\)。

对于 \(100\%\) 的数据，\(1\le n,m\le 10^5\)，\(1\le \sum |s|\le 5\times 10^5\)，\(1\le l\le r\le n\)，\(1\le k\le n\)。

不知道为什么要猫树分治。

首先建出 AC 自动机。

考虑根号分治，记 \(N = \sum |s|, B = \sqrt N\)。

如果 \(|s_k| \geq B\)，不同的 \(k\) 不会超过 \(B\) 个，对于每个 \(k\)，把该串在 AC 自动机上的每个点权值加 \(1\)，然后求出每个点的子树权值之和。这样就可以知道每个点在 \(s_k\) 的出现次数，用线段树维护区间最大值，这部分复杂度是 \(O((n+N)\sqrt N + m \log n)\)。

如果 \(|s_k| < B\)，考虑对 \(s_k\) 建立虚树，如果某个虚树上的点 \(x\) 到根的路径上存在某个 \([l, r]\) 的终止节点，说明答案至少是 \(siz_x\)（\(siz_x\) 表示虚树中 \(x\) 的子树大小）。

对 \(r\) 做扫描线，维护每个点到根的最大标号，如果这个标号 \(\geq l\) 说明合法，因此需要一个区间取 \(\max\)，单点查询的数据结构。可以用分块做到 \(O(\sqrt N) - O(1)\)。

这部分复杂度是 \(O(N\log N + (n+m)\sqrt N)\)。

最后修改于 2022-10-25