P3808 【模板】AC自动机(简单版)

    • 3.9K通过
    • 12.2K提交
  • 题目提供者 zcysky 管理员
  • 评测方式 云端评测
  • 标签 AC自动机 字符串 构造 高性能
  • 难度 提高+/省选-
  • 时空限制 500ms / 128MB

题解

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

    推荐的相关题目 显示

    题目背景

    通过套取数据而直接“打表”过题者,是作弊行为,发现即棕名。

    这是一道简单的AC自动机模板题。

    用于检测正确性以及算法常数。

    为了防止卡OJ,在保证正确的基础上只有两组数据,请不要恶意提交。

    管理员提示:本题数据内有重复的单词,且重复单词应该计算多次,请各位注意

    题目描述

    给定n个模式串和1个文本串,求有多少个模式串在文本串里出现过。

    输入输出格式

    输入格式:

    第一行一个n,表示模式串个数;

    下面n行每行一个模式串;

    下面一行一个文本串。

    输出格式:

    一个数表示答案

    输入输出样例

    输入样例#1: 复制
    2
    a
    aa
    aa
    输出样例#1: 复制
    2

    说明

    subtask1[50pts]:∑length(模式串)<=10^6,length(文本串)<=10^6,n=1;

    subtask2[50pts]:∑length(模式串)<=10^6,length(文本串)<=10^6;

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