P1872 回文串计数

    • 100通过
    • 265提交
  • 题目提供者 JosephZheng
  • 评测方式 云端评测
  • 标签
  • 难度 省选/NOI-
  • 时空限制 1000ms / 256MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    小a虽然是一名理科生,但他常常称自己是一名真正的文科生。不知为何,他对于背诵总有一种莫名其妙的热爱,这也促使他走向了以记忆量大而闻名的生物竞赛。然而,他很快发现这并不能满足他热爱背诵的心,但是作为一名强大的OIER,他找到了这么一个方法——背诵基因序列。然而这实在是太困难了,小啊感觉有些招架不住。不过他发现,如果他能事先知道这个序列里有多少对互不相交的回文串,他或许可以找到记忆的妙法。为了进一步验证这个想法,小a决定选取一个由小写字母构成的字符串SS来实验。由于互不相关的回文串实在过多,他很快就数晕了。不过他相信,在你的面前这个问题不过是小菜一碟。

    (1)对于字符串SS,设其长度为Len,那么下文用Si表示SS中第i个字符(1<=i<=Len)。

    (2)S[i,j]表示SS的一个子串,S[i,j]="SiSi+1Si+2...Sj-2Sj-1Sj",比如当SS为"abcgfd"时,S[2,5]="bcgf",S[1,5]="abcgf"。

    (3)当一个串被称为一个回文串当且仅当将这个串反写后与原串相同,如“abcba”。

    (4)考虑一个四元组(l,r,L,R),当S[l,r]和S[L,R]均为回文串时,且满足1<=l<=r<=L<=R<=Len时,我们称S[l,r]和S[L,R]为一对互不相交的回文串。即本题所求,也即为这种四元组的个数。两个四元组相同当且仅当对应的l,r,L,R都相同。

    输入输出格式

    输入格式:

    输入仅一行,为字符串SS,保证全部由小写字母构成,由换行符标志结束。

    50%的数据满足SS的长度不超过200;

    100%的数据满足SS的长度不超过2000。

    输出格式:

    仅一行,为一个整数,表示互不相关的回文串的对数。

    输入输出样例

    输入样例#1: 复制
    aaa
    输出样例#1: 复制
    5

    说明

    【样例数据说明】

    SS="aaa",SS的任意一个字符串均为回文串,其中总计有5对互不相关的回文串:

    (1,1,2,2),(1,1,2,3),(1,1,3,3),(1,2,3,3),(2,2,3,3)。

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