「CF232D」Fence-后缀数组+主席树

给定长度为 $n$ 的整数序列 $h[n]$ ,有 $Q$ 个询问,每次给出 $l_1,r_1$ ,​询问有多少对 $l_2,r_2$ ,满足以下条件:

  1. $r_2 – l_2 = r_1 – l_1$
  2. 区间 $[l_1, r_1]$ 与区间 $[l_2, r_2]$ 没有交集
  3. 对于任意 $i \in [0,r_1 – l_1]$ ,满足 $h[l_1 + i] + h[l_2 + i] = h[l_1] + h[l_2]$

「CF452E」Three strings-后缀数组

给出三个仅由小写字母构成的串 $A, B, C$ ,对于每个 $L \in [1, \min(len_A,len_B,len_C)]$ ,求满足$A[a,a+L-1] = B[b,b+L-1] = C[c,c+L-1]$ 的三元组 $(a,b,c)$ 的数量。

答案对 $1000000007 (10 ^ 9 + 7)$ 取模,字符总数小于 $3\times10^5$。

「JSOI2007」字符加密-后缀数组

喜欢钻研问题的 $JS$ 同学,最近又迷上了对加密方法的思考。一天,他突然想出了一种他认为是终极的加密办法:把需要加密的信息排成一圈,显然,它们有很多种不同的读法。

例如 JSOI07 ,可以读作: JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0 ,把它们按照字符串的大小排序:

  • 07JSOI
  • 7JSOI0
  • I07JSO
  • JSOI07
  • OI07JS
  • SOI07J

读出最后一列字符:I0O7SJ,就是加密后的字符串。 但是,如果想加密的字符串实在太长,你能写一个程序完成这个任务吗?

「BZOJ4278」[ONTAK2015]Tasowanie-后缀数组

给定两个数字串 $A$ 和 $B$ ,通过将 $A$ 和 $B$ 进行二路归并得到一个新的数字串 $T$ ,请找到字典序最小的 $T$ 。

「POI2010」Antisymmetry-后缀数组

对于一个 $0/1$ 字符串,如果将这个字符串 $0$ 和 $1$ 取反后,再将整个串反过来和原串一样,就称作“反对称”字符串。比如 $00001111$ 和 $010101$ 就是反对称的, $1001$ 就不是。

现在给出一个长度为 $n$ 的 $0/1$ 字符串,求它有多少个子串是反对称的。

「TJOI2013」单词-后缀数组+二分

可读版题意:

给定$n$个字符串,第$i$个字符串的长度为$M_i$,求每个字符串在所有字符串中出现的次数。

数据范围:$n \leq 100, M = \sum M_i \leq 10^6$.

「NOI2015」品酒大会-后缀数组

简单版题意:

给定一个长度为 $n$ 的字符串,和一个长度为 $n$ 的数列 $\{a_n\}$ ,求对于 $r$ 从 $0$ 到 $n-1$ ,所有满足 $1 \leq p < q \leq n$ 且 $lcp(p,q) \geq r$ 的数对个数以及满足上述条件的数对中 $a_p \times a_q$ 的最大值。( $a_i$ 可以为负数)

「HAOI2016」找相同字符-后缀数组+单调栈

给定两个字符串,求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。当这两个子串中只要有一个取得位置不同时,两个方案不同。

「NOI2016」优秀的拆分-后缀数组

如果一个字符串可以被拆分为 $AABB$ 的形式,其中 $A$ 和 $B$ 是任意非空字符串,则我们称该字符串的这种拆分是优秀的。一个字符串可能没有优秀的拆分,也可能存在不止一种优秀的拆分。

现在给出一个长度为 $n$ 的字符串 $S$ ,我们需要求出,在它所有子串的所有拆分方式中,优秀拆分的总个数。这里的子串是指字符串中连续的一段。

以下事项需要注意:

  • 出现在不同位置的相同子串,我们认为是不同的子串,它们的优秀拆分均会被记入答案。
  • 在一个拆分中,允许出现 $A = B$。例如 $cccc$ 存在拆分 $A = B = c$。
  • 字符串本身也是它的一个子串。

「TJOI2017」DNA-后缀数组

加里敦大学的生物研究所发现了决定人喜不喜欢吃藕的基因序列 $S$ ,有这个序列的碱基序列就会表现出喜欢吃藕的性状,但是研究人员发现对碱基序列 $S$ ,任意修改其中不超过 $3$ 个碱基,依然能够表现出吃藕的性状。现在研究人员想知道这个基因在 DNA 链 $S0$ 上的位置。所以你需要统计在一个表现出吃藕性状的人的 DNA 序列 $S0$ 上,有多少个连续子串可能是该基因,即有多少个 $S0$ 的连续子串修改小于等于三个字母能够变成 $S$ 。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×