P4482 [BJWC2018]Border 的四种求法

    • 79通过
    • 267提交
  • 题目提供者 Xeonacid
  • 评测方式 云端评测
  • 标签 2018 北京 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 5000ms / 512MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    Scape 一到机房,所有做题的人便都看着他笑,有的叫道,“Scape,你一定又被标准分倍杀了!”他不回答,对柜里说,“测两个程序,看一眼成绩单。”便拷出两个程序。他们又故意的高声嚷道,“你怎么欧拉回路和逆序对都WA了!”……

    题目描述

    Scape 知道,以上的故事只是 OI 生涯里的一个意外,为了证明自己,他决定教你 Border 的四种求法。

    给一个小写字母字符串 S ,q 次询问每次给出 l,r ,求 s[l..r] 的 Border 。

    Border: 对于给定的串 s ,最大的 i 使得 s[1..i] = s[|s|-i+1..|s|], |s| 为 s 的长度。

    输入输出格式

    输入格式:

    第一行一个字符串 S 。

    第二行一个整数 q 表示询问个数。

    接下来的 q 行每行两个整数 l,r 表示一个询问。

    输出格式:

    对于每组询问输出答案。

    输入输出样例

    输入样例#1: 复制
    abbabbaa
    3
    1 8
    1 7
    2 7
    输出样例#1: 复制
    1
    4
    3

    说明

    对于 30% 的数据, $n,q≤1000$ 。

    对于 50% 的数据, $n,q≤20000$ 。

    对于另外 30% 的数据,答案至少为 $r-l+1$ 的一半。

    对于 100% 的数据, $n,q≤2\cdot 10^5$ 。

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