Menci

眉眼如初,岁月如故

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


  1. 「CTSC2012」Cheat - SAM + 二分 + 单调队列 DP

    给出 m m 个串组成的「标准作文库」。对于任意一个串,如果它的长度不少于 L L 且在标准作文库中出现过,则它是「熟悉」的。对于任意一个串,如果能将它划分为若干个串,使「熟悉」的串的长度超过总长度的 90% 90\% ,则称这个串是「熟悉的文章」,定义 L0 L_0 为使这个串成为「熟悉的文章」的最大的 L L 。给出若干个串,求每个串的 L L 值。

    于  BZOJ, CTSC, DP, SAM, 二分, 单调队列, 字符串 继续阅读

  2. 「BZOJ 2555」SubString - SAM + LCT

    1. 在当前字符串的后面插入一个字符串;
    2. 询问字符串 s s 在当前字符串中出现了几次?(作为连续子串)

    于  BZOJ, Link-Cut Tree, SAM, 字符串, 数据结构 继续阅读

  3. 「TJOI2015」弦论 - SAM

    对于一个给定长度为 n n 的字符串,求它的字典序第 k k 小的子串。

    于  BZOJ, SAM, TJOI 继续阅读

  4. 「BZOJ 1396」识别子串 - SAM + 线段树

    对于一个字符串 S S ,和 S S 中的第 i i 个字符 x x ,定义子串 T=S(ij) T = S(i \ldots j) 为一个关于 x x 的识别子串,当且仅当:

    1. ixj i \leq x \leq j
    2. T T S S 中只出现一次。

    S S 关于每一位字符的最短识别子串长度。

    于  BZOJ, SAM, 李超树, 线段树 继续阅读

  5. 「SDOI2008」Sandy 的卡片 - 差分 + SAM

    相同的定义为:两个子串长度相同且一个串的全部元素加上一个数就会变成另一个串。给 n n 个串,求它们相同的子串最大长度。

    于  BZOJ, SAM, SDOI, 差分 继续阅读

  6. 「JSOI2012」玄武密码 - SAM

    给一个字符串 S S ,给一些字符串 si s_i ,求每个 si s_i 的最长的在 S S 中出现过的前缀的长度。

    于  BZOJ, JSOI, SAM, 字符串 继续阅读