{"problem":{"name":"F. Forbidden Indices","description":{"content":"You are given a string _s_ consisting of _n_ lowercase Latin letters. Some indices in this string are marked as _forbidden_. You want to find a string _a_ such that the value of |_a_|·_f_(_a_) is max","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF873F"},"statements":[{"statement_type":"Markdown","content":"You are given a string _s_ consisting of _n_ lowercase Latin letters. Some indices in this string are marked as _forbidden_.\n\nYou want to find a string _a_ such that the value of |_a_|·_f_(_a_) is maximum possible, where _f_(_a_) is the number of occurences of _a_ in _s_ such that these occurences end in non-forbidden indices. So, for example, if _s_ is _aaaa_, _a_ is _aa_ and index 3 is forbidden, then _f_(_a_) = 2 because there are three occurences of _a_ in _s_ (starting in indices 1, 2 and 3), but one of them (starting in index 2) ends in a forbidden index.\n\nCalculate the maximum possible value of |_a_|·_f_(_a_) you can get.\n\n## Input\n\nThe first line contains an integer number _n_ (1 ≤ _n_ ≤ 200000) — the length of _s_.\n\nThe second line contains a string _s_, consisting of _n_ lowercase Latin letters.\n\nThe third line contains a string _t_, consisting of _n_ characters _0_ and _1_. If _i_\\-th character in _t_ is _1_, then _i_ is a forbidden index (otherwise _i_ is not forbidden).\n\n## Output\n\nPrint the maximum possible value of |_a_|·_f_(_a_).\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"给你一个由 #cf_span[n] 个小写拉丁字母组成的字符串 #cf_span[s]。该字符串中的某些下标被标记为 _禁止的_。\n\n你希望找到一个字符串 #cf_span[a]，使得 #cf_span[|a|·f(a)] 的值尽可能大，其中 #cf_span[f(a)] 表示 #cf_span[a] 在 #cf_span[s] 中出现的次数，且这些出现必须以非禁止下标结尾。例如，若 #cf_span[s] 为 _aaaa_，#cf_span[a] 为 _aa_，且下标 #cf_span[3] 是禁止的，则 #cf_span[f(a) = 2]，因为 #cf_span[a] 在 #cf_span[s] 中有三个出现（分别起始于下标 #cf_span[1]、#cf_span[2] 和 #cf_span[3]），但其中有一个（起始于下标 #cf_span[2]）以禁止下标结尾。\n\n请计算你能获得的 #cf_span[|a|·f(a)] 的最大可能值。\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 200000]) —— #cf_span[s] 的长度。\n\n第二行包含一个字符串 #cf_span[s]，由 #cf_span[n] 个小写拉丁字母组成。\n\n第三行包含一个字符串 #cf_span[t]，由 #cf_span[n] 个字符 _0_ 和 _1_ 组成。若 #cf_span[t] 的第 #cf_span[i] 个字符是 _1_，则下标 #cf_span[i] 是禁止的（否则不是禁止的）。\n\n请输出 #cf_span[|a|·f(a)] 的最大可能值。\n\n## Input\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 200000]) —— #cf_span[s] 的长度。第二行包含一个字符串 #cf_span[s]，由 #cf_span[n] 个小写拉丁字母组成。第三行包含一个字符串 #cf_span[t]，由 #cf_span[n] 个字符 _0_ 和 _1_ 组成。若 #cf_span[t] 的第 #cf_span[i] 个字符是 _1_，则下标 #cf_span[i] 是禁止的（否则不是禁止的）。\n\n## Output\n\n请输出 #cf_span[|a|·f(a)] 的最大可能值。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of string $ s $.  \nLet $ s \\in \\Sigma^n $, where $ \\Sigma = \\{a, b, \\dots, z\\} $, be the input string.  \nLet $ t \\in \\{0,1\\}^n $ be the forbidden indices array: $ t[i] = 1 $ iff index $ i $ (1-based) is forbidden.  \n\nFor any non-empty substring $ a $ of $ s $, define:  \n- $ |a| $: length of $ a $,  \n- $ f(a) $: number of occurrences of $ a $ in $ s $ that end at a non-forbidden index.  \n\nAn occurrence of $ a $ starting at position $ i $ (1-based) ends at position $ i + |a| - 1 $.  \nThus, $ f(a) = \\left| \\left\\{ i \\in \\{1, \\dots, n - |a| + 1\\} \\mid s[i:i+|a|-1] = a \\text{ and } t[i + |a| - 1] = 0 \\right\\} \\right| $.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 200000 $  \n2. $ s $ consists of lowercase Latin letters.  \n3. $ t $ consists of characters '0' and '1'.\n\n**Objective**  \nMaximize $ |a| \\cdot f(a) $ over all non-empty substrings $ a $ of $ s $:  \n$$\n\\max_{\\substack{a \\text{ is a substring of } s \\\\ a \\neq \\varepsilon}} \\left( |a| \\cdot f(a) \\right)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF873F","tags":["dsu","string suffix structures","strings"],"sample_group":[["5\nababa\n00100","5"],["5\nababa\n00000","6"],["5\nababa\n11111","0"]],"created_at":"2026-03-03 11:00:39"}}