P4987 回文项链

    • 119通过
    • 730提交
  • 题目提供者 Forward_Star
  • 评测方式 云端评测
  • 标签 洛谷原创
  • 难度 省选/NOI-
  • 时空限制 500ms / 128MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    数据已增强,各位不要再交暴力了。

    国庆节期间,哥哥送了小埋一条项链。(假的,日本人过什么国庆。)

    然而小埋不太开心,她更想要买一部新手机玩游戏。

    题目描述

    不过小埋很快发现了项链的神奇之处。

    我们把项链看作一个$n$元环,记作$s$,环上每个结点由大写'A'-'Z'中的一个字母组成。小埋惊奇的发现,环上有很多回文串!我们定义回文串为环上一个首尾不重叠的连续子串(即环上每个结点最多被使用一次),且满足存在一个回文中心$i$,使得$i$之前的若干个字符分别与其关于$i$中心对称的字符相同。

    现在,小埋给出你这个环,并希望知道有多少长度为$l$的本质不同的回文串;我们认为两个回文串本质不同,当且仅当它们回文中心所在结点不同。

    输入输出格式

    输入格式:

    第一行,两个数表示$n$,$l$;

    接下来一行读入连续的$n$个字母,分别表示$s_1$,$s_2$,…,$s_n$;其中$s_i$与$s_i$ $_{mod}$ $_{n+1}$相邻。

    输出格式:

    一行,表示长度为$l$的回文串的个数。

    输入输出样例

    输入样例#1: 复制
    16 1
    XIAOMAITAIBANGLE
    输出样例#1: 复制
    16
    输入样例#2: 复制
    4 3
    ABAB
    输出样例#2: 复制
    4

    说明

    本题每个测试点时限500ms

    对于$30$%的数据,$n<=20$;

    对于$50$%的数据,$n<=200$;

    对于$80$%的数据,$n<=2000$;

    对于$100$%的数据,$n<=10^6$,$0<l<=n$且$l$为奇数。

    仔细读题,本题回文串与传统意义上的回文串不同。

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