CF7D.Palindrome Degree
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
String s of length n is called k -palindrome, if it is a palindrome itself, and its prefix and suffix of length are (k−1) -palindromes. By definition, any string (even empty) is 0-palindrome.
Let's call the palindrome degree of string s such a maximum number k , for which s is k -palindrome. For example, "abaaba" has degree equals to 3 .
You are given a string. Your task is to find the sum of the palindrome degrees of all its prefixes.
回文度
题目描述
前置知识:一个字符串与这个字符串反转后相等,则这个字符串是一个回文字符串。
一个长度为n的字符串s叫做k-palindrome当这个字符串是一个回文字符串。与此同时,这个字符串的长度为⌈n/2⌉被称之为k−1-palindromes。根据定义,任何字符串(包括但不限于空字符串)也是0-palindrome。
一个字符串的回文度是一个字符串中最长的回文字串的长度。例如字符串”abaabc”
的度即位3。
你的任务是找出这个字符串的所有前缀的回文度之和。
感谢Macw提供翻译
输入格式
The first line of the input data contains a non-empty string, consisting of Latin letters and digits. The length of the string does not exceed 5⋅106 . The string is case-sensitive.
输入一行一个长度不超过5∗106的字符串。保证字符串仅包括拉丁大小写字符以及数字字符。该字符串是大小写敏感的。
输出格式
Output the only number — the sum of the polindrome degrees of all the string's prefixes.
输出一行一个整数,表示输入字符串的所有前缀的回文度之和。
输入输出样例
输入#1
a2A
输出#1
1
输入#2
abacaba
输出#2
6
说明/提示
请注意,本题的空间限制为256MB,是默认空间限制的两倍