D. Palindrome Degree

Codeforces

IDCF7D

Time1000ms

Memory256MB

Difficulty—

hashingstrings

English · Original

Chinese · Translation

Formal · Original

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. ## Input 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. ## Output Output the only number — the sum of the polindrome degrees of all the string's prefixes. [samples]

长度为 #cf_span[n] 的字符串 #cf_span[s] 被称为 #cf_span[k]-回文串，当且仅当它本身是回文串，且其长度为 #cf_span[(k - 1)] 的前缀和后缀都是 #cf_span[(k - 1)]-回文串。根据定义，任意字符串（包括空字符串）都是 0-回文串。我们定义字符串 #cf_span[s] 的回文度为最大的数 #cf_span[k]，使得 #cf_span[s] 是 #cf_span[k]-回文串。例如，"_abaaba_" 的回文度为 #cf_span[3]。给你一个字符串，你的任务是求出它的所有前缀的回文度之和。输入数据的第一行包含一个非空字符串，由拉丁字母和数字组成。字符串长度不超过 #cf_span[5·106]。字符串区分大小写。请输出一个数——该字符串所有前缀的回文度之和。 ## Input 输入数据的第一行包含一个非空字符串，由拉丁字母和数字组成。字符串长度不超过 #cf_span[5·106]。字符串区分大小写。 ## Output 请输出一个数——该字符串所有前缀的回文度之和。 [samples]

**Definitions** Let $ s $ be a string of length $ n $. For $ k \in \mathbb{N}_0 $, define that $ s $ is a **$ k $-palindrome** if: - $ k = 0 $: always true (by definition), - $ k \geq 1 $: $ s $ is a palindrome **and** its prefix (and suffix) of length $ \lfloor |s|/2 \rfloor $ is a $ (k-1) $-palindrome. Let $ d(s) $ denote the **palindrome degree** of string $ s $: the maximum $ k $ such that $ s $ is a $ k $-palindrome. **Constraints** - $ 1 \leq |s| \leq 5 \cdot 10^6 $ - $ s $ consists of Latin letters and digits (case-sensitive) **Objective** Compute: $$ \sum_{i=1}^{n} d(s[1:i]) $$ where $ s[1:i] $ denotes the prefix of $ s $ of length $ i $.

Samples

Input #1

a2A

Output #1

Input #2

abacaba

Output #2

API Response (JSON)

{
  "problem": {
    "name": "D. Palindrome Degree",
    "description": {
      "content": "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",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF7D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "长度为 #cf_span[n] 的字符串 #cf_span[s] 被称为 #cf_span[k]-回文串，当且仅当它本身是回文串，且其长度为 #cf_span[(k - 1)] 的前缀和后缀都是 #cf_span[(k - 1)]-回文串。根据定义，任意字符串（包括空字符串）都是 0-回文串。\n\n我们定义字符串 #cf_span[s] 的回文度为最大的数 #cf_span[k]，使得 #cf_sp...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s $ be a string of length $ n $.  \nFor $ k \\in \\mathbb{N}_0 $, define that $ s $ is a **$ k $-palindrome** if:  \n- $ k = 0 $: always true (by definition),  \n- $ k \\geq 1 $: $ s...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments