Menci

眉眼如初,岁月如故

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


  1. 「Codeforces 808G」Anthem of Berland - KMP + DP

    给一个含有字母以及 ?s s 串和一个含有字母的 t t 串,其中 ? 可以匹配任何字符,求 s s 串最多匹配 t t 串多少次。

    于  Codeforces, DP, KMP, 字符串 继续阅读

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

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

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

  3. 「BZOJ 2555」SubString - SAM + LCT

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

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

  4. 「JSOI2012」玄武密码 - SAM

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

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

  5. 「SCOI2016」背单词 - Trie + 贪心

    总共有 n n 个单词,对于一个序号为 x x 的单词(序号 1x1 1 \ldots x - 1 都已经被填入):

    1. 如果存在一个单词是它的后缀,并且当前没有被填入表内,代价为 n×n n \times n 颗泡椒才能学会;
    2. 当它的所有后缀都被填入表内的情况下,如果在 1x1 1 \ldots x - 1 的位置上的单词都不是它的后缀,那么代价为 x x
    3. 当它的所有后缀都被填入表内的情况下,如果 1x1 1 \ldots x - 1 的位置上存在是它后缀的单词,所有是它后缀的单词中,序号最大为 y y ,那么代价为 xy x - y

    于  BZOJ, SCOI, Trie, 字符串, 贪心 继续阅读

  6. 后缀自动机学习笔记

    后缀自动机是一种有限状态自动机,它可以(且仅可以)接受一个字符串的所有后缀

    于  后缀自动机, 字符串, 学习笔记, 算法模板 继续阅读

  7. Manacher 学习笔记

    Manacher 可在 O(n) O(n) 的时间内求出一个字符串以每个位置为中心的最长回文子串。

    于  Manacher, 字符串, 学习笔记, 算法模板 继续阅读

  8. 「BZOJ 2565」最长双回文串 - Manacher

    输入串 S S ,求 S S 的最长双回文子串 T T ,即可将 T T 分为两部分 X X Y Y X,Y1 |X|, |Y| \geq 1 )且 X X Y Y 都是回文串。

    于  BZOJ, Manacher, 字符串 继续阅读

  9. 「POJ 3630」Phone List - Trie

    n n 个字符串,求有没有一个字符串是另一个字符串的前缀。

    于  POJ, Trie, 字符串 继续阅读

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

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

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