Menci

眉眼如初,岁月如故

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


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

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

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

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

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

  3. AC 自动机学习笔记

    AC 自动机是一种多模式串匹配算法,可以用来在文本串中匹配一系列模式串,其时间复杂度与串的总长度成正比。

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

  4. 「JSOI2009」有趣的游戏 - AC 自动机 + 概率与期望

    现有 n n 个单词,均由前 m m 个大写字母组成。每一时刻随机产生一个字母,产生第 i i 个字母的概率为 piqi(0piqi) {p_i \over q_i} (0 \leq p_i \leq q_i) T T 时刻后会产生一个长度为 T T 的串。

    如果某个时刻,有一个单词在这个串中出现了,则过程结束。求产生的串中出现每个单词的概率。

    于  AC 自动机, BZOJ, JSOI, 字符串, 数学, 概率与期望, 高斯消元 继续阅读

  5. 「BZOJ 3881」Divljak - AC 自动机 + 树上路径并

    n n 个字符串 S1,S2,,Sn S_1, S_2, \ldots, S_n ,另有一个集合 T T ,初始为空。
    q q 次操作,每次向 T T 中添加一个字符串 P P ,或询问 T T 中有多少串能匹配 Si S_i

    于  AC 自动机, BZOJ, COCI, 字符串, 树上路径并, 树链剖分 继续阅读

  6. 「BZOJ 2580」Video Game - AC 自动机

    给出 n n 个串 si s_i ,求一个长度为 k k 的串 S S ,使 S S 匹配 si s_i (可重叠)的次数最多。

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

  7. 「BZOJ 3940」Censoring - AC 自动机

    给定一个串 S S 和一些单词串,每一次在 S S 中寻找第一次出现的单词串,并将其删除,求最终串。

    于  AC 自动机, BZOJ, USACO, 字符串, , 链表 继续阅读

  8. 「BeiJing2011」矩阵模板 - AC 自动机

    给定一个 M M N N 列的 01 矩阵,以及 Q Q A A B B 列的 01 矩阵,你需要求出这 Q Q 个矩阵哪些在原矩阵中出现过。

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

  9. 「POI2000」病毒 - AC 自动机 + 拓扑排序

    二进制病毒审查委员会最近发现了如下的规律:某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码,那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段,试问,是否存在一个无限长的安全的二进制代码。

    于  AC 自动机, BZOJ, POI, 字符串, 拓扑排序 继续阅读

  10. 「NOI2011」阿狸的打字机 - AC 自动机

    打字机上只有 28 28 个按键,分别印有 26 26 个小写英文字母和 BP 两个字母。

    经阿狸研究发现,这个打字机是这样工作的:

    • 输入小写字母,打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。
    • 按一下印有 B 的按键,打字机凹槽中最后一个字母会消失。
    • 按一下印有 P 的按键,打字机会在纸上打印出凹槽中现有的所有字母并换行,但凹槽中的字母不会消失。

    我们把纸上打印出来的字符串从 1 1 开始顺序编号,一直到 n n 。打字机有一个非常有趣的功能,在打字机中暗藏一个带数字的小键盘,在小键盘上输入两个数 (x,y) (x, y) (其中 1x,yn 1 \leq x, y \leq n ),打字机会显示第 x x 个打印的字符串在第 y y 个打印的字符串中出现了多少次。

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