Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


  1. 「HDU 5906」Square Revolution - 后缀数组 + 并查集 + 树状数组

    对于一个给定的字符串 S S ,有多少连续子串是 prefix-suffix-square free 的。

    一个字符串被称为 square 当且仅当它可以由两个相同的串连接而成。例如,ababaa 是 square,而 aaaabba 不是。一个字符串是 prefix-suffix-square free 的当且仅当他的任何前缀或者后缀都不是 square。

    于  Bestcoder, HDU, 后缀数组, 字符串, 并查集, 树状数组, 离线 继续阅读

  2. 「BZOJ 3796」Mushroom - 后缀数组 + AC 自动机

    给三个字符串 s1,s2,s3 s_1, s_2, s_3 ,求一个长度最大的 w w ,满足:

    1. w w s1 s_1 的子串;
    2. w w s2 s_2 的子串;
    3. s3 s_3 不是 w w 的子串;

    于  AC 自动机, BZOJ, 后缀数组, 字符串 继续阅读

  3. 「BZOJ 3277」串 - 后缀数组 + 并查集 + 启发式合并

    n n 个字符串,询问每个字符串有多少子串(不要求本质不同,不包括空串)是所有 n n 个字符串中至少 k k 个字符串的子串。

    于  BZOJ, Codeforces, 后缀数组, 启发式合并, 字符串, 并查集 继续阅读

  4. 「BZOJ 3230」相似子串 - 后缀数组

    对于一个长度为 N N 的字符串 S S ,将其本质不同的所有子串按照字典序排序。我们定义两个子串的相似程度为 f=a2+b2 f = a ^ 2 + b ^ 2 的最大值,其中 a a b b 满足:S[ll+a1]=S[pp+a1] S[l \ldots l + a - 1] = S[p \ldots p + a - 1] S[rb+1r]=S[qb+1q] S[r - b + 1 \ldots r] = S[q - b + 1 \ldots q] 0arl+1 0 \leq a \leq r - l + 1 0bqp+1 0 \leq b \leq q - p + 1

    每次询问排序后的第 i i 个和第 j j 个子串的相似程度。

    于  BZOJ, 后缀数组, 字符串 继续阅读

  5. 「BZOJ 1692」队列变换 - 后缀数组 + 贪心

    对于一个字符串 S S ,每次从它的首部或尾部弹出一个字符,加入到 T T 的尾部,求可以构造出的字典序最小的 T T

    于  BZOJ, USACO, 后缀数组, 字符串, 贪心 继续阅读

  6. 「AHOI2013」差异 - 后缀数组

    一个长度为 n n 的字符串,令 Ti T_i 表示它从第 i i 个字符开始的后缀,求

    1i<jnlen(Ti)+len(Tj)2×lcp(Ti,Tj) \sum\limits_{1 \leq i < j \leq n} \mathrm{len}(T_i) + \mathrm{len}(T_j) - 2 \times \mathrm{lcp}(T_i, T_j)

    于  AHOI, BZOJ, 单调栈, 后缀数组, 字符串 继续阅读

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

    把一个字符串 S S 排成一圈,从每个字符开始读一圈,把每次读到的字符串排序,按顺序将每个串的最后一个字符排成一个新字符串,求新字符串。

    于  BZOJ, JSOI, 后缀数组, 字符串 继续阅读

  8. 「NOI2015」品酒大会 - 后缀数组 + 并查集

    给定字符串 S S 和序列 f(i) f(i) ,对于 r[0, n1] r \in [0,\ n - 1] ,求:

    1. 满足 LCP(suffix(i), suffix(j))r \mathrm {LCP}(\mathrm{suffix}(i),\ \mathrm{suffix}(j)) \geq r 的无序二元组 (i, j) (i,\ j) 数量;
    2. 上述二元组 (i,j) (i, j) 使 f(i)×f(j) f(i) \times f(j) 取得的最大值。

    于  BZOJ, NOI, 后缀数组, 字符串, 并查集 继续阅读

  9. 「SDOI2016」生成魔咒 - 后缀数组

    魔咒串由许多魔咒字符组成,魔咒字符可以用数字表示。例如可以将魔咒字符 1 1 2 2 拼凑起来形成一个魔咒串 [1,2] [1, 2]
    一个魔咒串 S S 的非空字串被称为魔咒串 S S 的生成魔咒。
    例如 S=[1,2,1] S = [1, 2, 1] 时,它的生成魔咒有 [1] [1] [2] [2] [1,2] [1, 2] [2,1] [2, 1] [1,2,1] [1, 2, 1] 五种。S=[1,1,1] S = [1, 1, 1] 时,它的生成魔咒有 [1] [1] [1,1] [1, 1] [1,1,1] [1, 1, 1] 三种。
    最初 S S 为空串。共进行 n n 次操作,每次操作是在 S S 的结尾加入一个魔咒字符。每次操作后都需要求出,当前的魔咒串 S S 共有多少种生成魔咒。

    于  BZOJ, COGS, RMQ, SDOI, 后缀数组, 字符串 继续阅读

  10. 「SPOJ 694」Distinct Substrings - 后缀数组

    给定一个字符串,求该字符串含有的本质不同的子串数量。

    于  SPOJ, 后缀数组, 字符串 继续阅读