P2336 [SCOI2012]喵星球上的点名

    • 146通过
    • 442提交
  • 题目提供者 xmyzwls 管理员
  • 评测方式 云端评测
  • 标签 AC自动机 后缀数组,SA 莫队 各省省选 2012 四川 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    a180285 幸运地被选做了地球到喵星球的留学生。他发现喵星人在上课前的点名现象非常有趣。

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

    然而,由于喵星人的字码过于古怪,以至于不能用 ASCII 码来表示。为了方便描述,a180285 决定用数串来表示喵星人的名字。

    现在你能帮助 a180285 统计每次点名的时候有多少喵星人答到,以及 M 次点名结束后每个喵星人答到多少次吗?

    输入输出格式

    输入格式:

    现在定义喵星球上的字符串给定方法:

    先给出一个正整数 L ,表示字符串的长度,接下来L个整数表示字符串的每个字符。

    输入的第一行是两个整数 N 和 M。

    接下来有 N 行, 每行包含第 i 个喵星人的姓和名两个串。 姓和名都是标准的喵星球上的字符串。

    接下来有 M 行,每行包含一个喵星球上的字符串,表示老师点名的串。

    输出格式:

    对于每个老师点名的串输出有多少个喵星人应该答到。

    然后在最后一行输出每个喵星人被点到多少次。

    输入输出样例

    输入样例#1: 复制
    2 3
    6 8 25 0 24 14 8 6 18 0 10 20 24 0
    7 14 17 8 7 0 17 0 5 8 25 0 24 0
    4 8 25 0 24
    4 7 0 17 0
    4 17 0 8 25
    输出样例#1: 复制
    2
    1
    0
    1 2

    说明

    事实上样例给出的数据如果翻译成地球上的语言可以这样来看

    2 3 izayoi sakuya

    orihara izaya

    izay hara raiz

    对于 30%的数据,保证:

    1<=N,M<=1000,喵星人的名字总长不超过 4000,点名串的总长不超过 2000,

    对于 100%的数据,保证:

    1<=N<=20000 ,1<=M<=50000. 喵星人的名字总长和点名串的总长分别不超过100000,保证喵星人的字符串中作为字符存在的数不超过 10000

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。