Menci

眉眼如初,岁月如故

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


  1. 「JSOI2008」火星人 - Splay + Hash

    给定一个字符串,每次修改一个字符、插入一个字符、查询某两个后缀的最长公共前缀。

    于  BZOJ, Hash, JSOI, Splay, 字符串 继续阅读

  2. 「HNOI2008」GT考试 - KMP + 矩阵乘法

    给一个长度为 m m 的字符串 T T ,求长度为 n n 且不包含 T T 的字符串的数量。

    于  BZOJ, DP, HNOI, KMP, 字符串, 快速幂, 矩阵乘法 继续阅读

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

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

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

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

  4. 「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, 后缀数组, 字符串 继续阅读

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

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

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

  6. 「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, 后缀数组, 字符串 继续阅读

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

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

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

  8. 「SCOI2012」喵星球上的点名 - AC 自动机

    假设课堂上有 N N 个喵星人,每个喵星人的名字由姓和名构成。喵星球上的老师会选择 M M 个串来点名,每次读出一个串的时候,如果这个串是一个喵星人的姓或名的子串,那么这个喵星人就必须答到。

    统计每次点名的时候有多少喵星人答到,以及 M M 次点名结束后每个喵星人答到多少次。

    于  AC 自动机, BZOJ, SCOI, 字符串 继续阅读

  9. 「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, 单调栈, 后缀数组, 字符串 继续阅读

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

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

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