P4770 [NOI2018]你的名字

    • 606通过
    • 2.8K提交
  • 题目提供者 chen_zhe Aya
  • 评测方式 云端评测
  • 标签 后缀数组,SA 后缀自动机,SAM 线段树 NOI系列 2018 O2优化 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 5000ms / 1280MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    实力强大的小A 被选为了ION2018 的出题人,现在他需要解决题目的命名问题。

    题目描述

    小A 被选为了ION2018 的出题人,他精心准备了一道质量十分高的题目,且已经把除了题目命名以外的工作都做好了。

    由于ION 已经举办了很多届,所以在题目命名上也是有规定的,ION 命题手册规定:每年由命题委员会规定一个小写字母字符串,我们称之为那一年的命名串,要求每道题的名字必须是那一年的命名串的一个非空连续子串,且不能和前一年的任何一道题目的名字相同。

    由于一些特殊的原因,小A 不知道ION2017 每道题的名字,但是他通过一些特殊手段得到了ION2017 的命名串,现在小A 有Q 次询问:每次给定ION2017 的命名串和ION2018 的命名串,求有几种题目的命名,使得这个名字一定满足命题委员会的规定,即是ION2018 的命名串的一个非空连续子串且一定不会和ION2017 的任何一道题目的名字相同。

    由于一些特殊原因,所有询问给出的ION2017 的命名串都是某个串的连续子串,详细可见输入格式。

    输入输出格式

    输入格式:

    第一行一个字符串S ,之后询问给出的ION2017 的命名串都是S 的连续子串。 第二行一个正整数Q,表示询问次数。 接下来Q 行,每行有一个字符串T 和两个正整数$l,r$,表示询问如果ION2017 的 命名串是$S [l..r]$,ION2018 的命名串是T 的话,有几种命名方式一定满足规定。

    输出格式:

    输出Q 行,第i 行一个非负整数表示第i 个询问的答案。

    输入输出样例

    输入样例#1: 复制
    scbamgepe
    3
    smape 2 7
    sbape 3 8
    sgepe 1 9
    输出样例#1: 复制
    12
    10
    4

    说明

    测试点 $|S|\leq$ $Q\leq $ $\sum |T|\leq $ 其他限制
    1 $200$ $200$ $40000$ $|T|\leq 200$
    2 $1000$ $200$ $40000$ $|T|\leq 200$
    3 $1000$ $200$ $40000$ $|T|\leq 200$
    4 $1000$ $200$ $5 \times 10^5$
    5 $1000$ $200$ $5 \times 10^5$
    6 $5 \times 10^5$ $1$ $5 \times 10^5$
    7 $5 \times 10^5$ $1$ $5 \times 10^5$
    8 $10^5$ $10^5$ $2 \times 10^5$
    9 $10^5$ $10^5$ $2 \times 10^5$ 字符串随机
    10 $2 \times 10^5$ $10^5$ $4 \times 10^5$
    11 $2 \times 10^5$ $10^5$ $4 \times 10^5$ 字符串随机
    12 $3 \times 10^5$ $10^5$ $6 \times 10^5$
    13 $3 \times 10^5$ $10^5$ $6 \times 10^5$ 字符串随机
    14 $4 \times 10^5$ $10^5$ $8 \times 10^5$
    15 $4 \times 10^5$ $10^5$ $8 \times 10^5$ 字符串随机
    16 $5 \times 10^5$ $10^5$ $10^6$
    17 $5 \times 10^5$ $10^5$ $10^6$ 字符串随机
    18 $2 \times 10^5$ $10^5$ $10^6$
    19 $3 \times 10^5$ $10^5$ $10^6$
    20 $4 \times 10^5$ $10^5$ $10^6$
    21 $5 \times 10^5$ $10^5$ $10^6$
    22 $5 \times 10^5$ $10^5$ $10^6$
    23 $5 \times 10^5$ $10^5$ $10^6$
    24 $5 \times 10^5$ $10^5$ $10^6$
    25 $5 \times 10^5$ $10^5$ $10^6$

    对于前17个测试点的所有询问有$l=1,r=|S|$

    对于所有数据,保证 $1\leq l \leq r \leq |S|$,$1\leq |T|\leq 5 \times 10^5$

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