{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"秋实大哥喜欢探索新鲜事物,最近他发明了一种新型回文串,叫K重回文串!今天他想用它来考考小朋友们。\n\n秋实大哥给出了与$K$重回文串有关的信息\n\u003e#####任何字符串都属于0重回文串,包括空字符串。\n\u003e#####一个长度为$N$的字符串$S$,$S$是$K(k \\geq 1)$重回文串,当且仅当$S$是回文串,且其长度为$\\lfloor \\frac{N}{2} \\rfloor$的前缀和长度为$\\lfloor \\frac{N}{2} \\rfloor$的后缀是$K-1$重回文串。\n\u003e#####如果一个字符串是$K$重回文串,则称该字符串有一个回文值为$K$。一个字符串可以有多个回文值,比如$S\u003dabaaba$,其回文值可为0,1,2,3。\n\u003e#####字符串的最大回文值是该字符串所有回文值的最大值。\n\u003e#####若字符串$S$的最大回文值$ \\geq 1$,则$S$一定是回文串。\n\u003e#####一个字符串$S$,如果其正着读和反着读是一样的,则称$S$是回文串,比如aabaa,aba,a。但abc,abab,aacba就不是回文串。\n\u003e#####一个长度为$N$的字符串$S$,其有$N+1$个前缀和$N+1$个后缀(不一定非空),比如abcde,有6个前缀,分别是空字符串,a,ab,abc,abcd,abcde;有6个后缀,分别是空字符串,e,de,cde,bcde,abcde。\n\n####秋实大哥给你一个字符串$S$,他想问问你,$S$所有前缀的最大回文值之和是多少?"}},{"title":"Input","value":{"format":"MD","content":"第一行输入一个字符串$S(0\u003c|S| \\leq 2\\cdot 10^6)$,$S$包含 大写英文字母(A-Z),小写英文字母(a-z),数字(0-9)"}},{"title":"Output","value":{"format":"MD","content":"输出一个整数,表示$S$所有前缀的最大回文值之和。"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003ez\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 2","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003ea2Az\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 3","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003eabacaba\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 4","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003eCCeCeCCCee\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Sample 5","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003eZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e231\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"MD","content":"#####下面对样例3进行解释:\n\n\u003e#####abacaba有8个前缀,分别是 空字符串,a,ab,aba,abac,abaca,abacab,abacaba;\n\n\u003e#####设P(i) 表示第 i 个前缀的最大回文值,且空字符串是第0个前缀;\n\n\u003e#####则P(0)\u003d0,P(1)\u003d1,P(2)\u003d0,P(3)\u003d2,P(4)\u003d0,P(5)\u003d0,P(6)\u003d0,P(7)\u003d3;那么$\\sum_{i\u003d0}^7 P(i)\u003d6$。"}}]}