{"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.\n\nLet'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.\n\nYou are given a string. Your task is to find the sum of the palindrome degrees of all its prefixes.\n\n## Input\n\nThe 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.\n\n## Output\n\nOutput the only number — the sum of the polindrome degrees of all the string's prefixes.\n\n[samples]","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_span[s] 是 #cf_span[k]-回文串。例如，\"_abaaba_\" 的回文度为 #cf_span[3]。\n\n给你一个字符串，你的任务是求出它的所有前缀的回文度之和。\n\n输入数据的第一行包含一个非空字符串，由拉丁字母和数字组成。字符串长度不超过 #cf_span[5·106]。字符串区分大小写。\n\n请输出一个数——该字符串所有前缀的回文度之和。\n\n## Input\n\n输入数据的第一行包含一个非空字符串，由拉丁字母和数字组成。字符串长度不超过 #cf_span[5·106]。字符串区分大小写。\n\n## Output\n\n请输出一个数——该字符串所有前缀的回文度之和。\n\n[samples]","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 a palindrome **and** its prefix (and suffix) of length $ \\lfloor |s|/2 \\rfloor $ is a $ (k-1) $-palindrome.  \n\nLet $ d(s) $ denote the **palindrome degree** of string $ s $: the maximum $ k $ such that $ s $ is a $ k $-palindrome.\n\n**Constraints**  \n- $ 1 \\leq |s| \\leq 5 \\cdot 10^6 $  \n- $ s $ consists of Latin letters and digits (case-sensitive)  \n\n**Objective**  \nCompute:  \n$$\n\\sum_{i=1}^{n} d(s[1:i])\n$$  \nwhere $ s[1:i] $ denotes the prefix of $ s $ of length $ i $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF7D","tags":["hashing","strings"],"sample_group":[["a2A","1"],["abacaba","6"]],"created_at":"2026-03-03 11:00:39"}}