{"problem":{"name":"F. k-substrings","description":{"content":"You are given a string _s_ consisting of _n_ lowercase Latin letters. Let's denote _k_\\-substring of _s_ as a string _subs__k_ = _s__k__s__k_ + 1.._s__n_ + 1 - _k_. Obviously, _subs_1 = _s_, and ther","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF961F"},"statements":[{"statement_type":"Markdown","content":"You are given a string _s_ consisting of _n_ lowercase Latin letters.\n\nLet's denote _k_\\-substring of _s_ as a string _subs__k_ = _s__k__s__k_ + 1.._s__n_ + 1 - _k_. Obviously, _subs_1 = _s_, and there are exactly such substrings.\n\nLet's call some string _t_ an **odd proper suprefix** of a string _T_ iff the following conditions are met:\n\n*   |_T_| > |_t_|;\n*   |_t_| is an odd number;\n*   _t_ is simultaneously a prefix and a suffix of _T_.\n\nFor evey _k_\\-substring () of _s_ you have to calculate the maximum length of its odd proper suprefix.\n\n## Input\n\nThe first line contains one integer _n_ (2 ≤ _n_ ≤ 106) — the length _s_.\n\nThe second line contains the string _s_ consisting of _n_ lowercase Latin letters.\n\n## Output\n\nPrint integers. _i_\\-th of them should be equal to maximum length of an odd proper suprefix of _i_\\-substring of _s_ (or  - 1, if there is no such string that is an odd proper suprefix of _i_\\-substring).\n\n[samples]\n\n## Note\n\nThe answer for first sample test is folowing:\n\n*   1-substring: bcabca**bca****bcabca**\n*   2-substring: cabcab**c****abcabc**\n*   3-substring: abcabc**abcab**\n*   4-substring: bcabca**bca**\n*   5-substring: cabcab**c**\n*   6-substring: abcab\n*   7-substring: bca\n*   8-substring: c","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"你被给定一个由 #cf_span[n] 个小写拉丁字母组成的字符串 #cf_span[s]。\n\n记 #cf_span[k]-子串 为字符串 #cf_span[subsk = sksk + 1..sn + 1 - k]。显然，#cf_span[subs1 = s]，并且恰好存在这样的子串。\n\n称某个字符串 #cf_span[t] 为字符串 #cf_span[T] 的 *奇数真前缀*，当且仅当满足以下条件：\n\n对于 #cf_span[s] 的每一个 #cf_span[k]-子串，你需要计算其奇数真前缀的最大长度。\n\n第一行包含一个整数 #cf_span[n] #cf_span[(2 ≤ n ≤ 106)] —— 字符串 #cf_span[s] 的长度。\n\n第二行包含由 #cf_span[n] 个小写拉丁字母组成的字符串 #cf_span[s]。\n\n请输出 #cf_span[n/2] 个整数。第 #cf_span[i] 个整数应等于 #cf_span[s] 的第 #cf_span[i]-子串的奇数真前缀的最大长度（如果不存在这样的奇数真前缀，则输出 #cf_span[ - 1]）。\n\n## Input\n\n第一行包含一个整数 #cf_span[n] #cf_span[(2 ≤ n ≤ 106)] —— 字符串 #cf_span[s] 的长度。第二行包含由 #cf_span[n] 个小写拉丁字母组成的字符串 #cf_span[s]。\n\n## Output\n\n请输出 #cf_span[n/2] 个整数。第 #cf_span[i] 个整数应等于 #cf_span[s] 的第 #cf_span[i]-子串的奇数真前缀的最大长度（如果不存在这样的奇数真前缀，则输出 #cf_span[ - 1]）。\n\n[samples]\n\n## Note\n\n第一个样例的答案如下：\n\n1-子串：#cf_span(class=[tex-font-style-underline], body=[bcabca*bca*])*bcabca*\n\n2-子串：#cf_span(class=[tex-font-style-underline], body=[cabcab*c*])*abcabc*\n\n3-子串：#cf_span(class=[tex-font-style-underline], body=[abcab])c*abcab*\n\n4-子串：#cf_span(class=[tex-font-style-underline], body=[bca])bca*bca*\n\n5-子串：#cf_span(class=[tex-font-style-underline], body=[c])abcab*c*\n\n6-子串：abcab\n\n7-子串：bca\n\n8-子串：c","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 10^6 $.  \nLet $ s = s_1 s_2 \\dots s_n $ be a string of length $ n $ over the alphabet of lowercase Latin letters.  \n\nFor each $ k \\in \\{1, 2, \\dots, \\lfloor \\frac{n+1}{2} \\rfloor\\} $, define the $ k $-substring:  \n$$\ns^{(k)} = s_k s_{k+1} \\dots s_{n+1-k}\n$$  \nNote: $ s^{(1)} = s $, and $ s^{(k)} $ has length $ n - 2(k - 1) $.\n\nA string $ t $ is an *odd proper suprefix* of a string $ T $ if:  \n- $ t $ is a prefix of $ T $,  \n- $ t $ is also a suffix of $ T $,  \n- $ t \\neq T $ (proper),  \n- $ |t| $ is odd.\n\n**Constraints**  \n1. $ 2 \\leq n \\leq 10^6 $  \n2. $ s_i \\in \\{a, b, \\dots, z\\} $ for all $ i \\in \\{1, \\dots, n\\} $\n\n**Objective**  \nFor each $ k \\in \\{1, 2, \\dots, \\lfloor \\frac{n+1}{2} \\rfloor\\} $, compute:  \n$$\nL_k = \\max \\left\\{ \\ell \\in \\mathbb{Z}^+ \\mid \\ell \\text{ is odd},\\; \\ell < |s^{(k)}|,\\; s^{(k)}[1..\\ell] = s^{(k)}[|s^{(k)}|-\\ell+1..|s^{(k)}|] \\right\\}\n$$  \nIf no such $ \\ell $ exists, set $ L_k = -1 $.\n\nOutput the sequence $ L_1, L_2, \\dots, L_{\\lfloor (n+1)/2 \\rfloor} $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF961F","tags":["binary search","hashing","string suffix structures"],"sample_group":[["15\nbcabcabcabcabca","9 7 5 3 1 -1 -1 -1"],["24\nabaaabaaaabaaabaaaabaaab","15 13 11 9 7 5 3 1 1 -1 -1 1"],["19\ncabcabbcabcabbcabca","5 3 1 -1 -1 1 1 -1 -1 -1"]],"created_at":"2026-03-03 11:00:39"}}