F. Forbidden Indices

Codeforces

IDCF873F

Time2000ms

Memory256MB

Difficulty—

dsustring suffix structuresstrings

English · Original

Chinese · Translation

Formal · Original

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 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. Calculate the maximum possible value of |_a_|·_f_(_a_) you can get. ## Input The first line contains an integer number _n_ (1 ≤ _n_ ≤ 200000) — the length of _s_. The second line contains a string _s_, consisting of _n_ lowercase Latin letters. The 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). ## Output Print the maximum possible value of |_a_|·_f_(_a_). [samples]

给你一个由 #cf_span[n] 个小写拉丁字母组成的字符串 #cf_span[s]。该字符串中的某些下标被标记为 _禁止的_。你希望找到一个字符串 #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]）以禁止下标结尾。请计算你能获得的 #cf_span[|a|·f(a)] 的最大可能值。第一行包含一个整数 #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] 是禁止的（否则不是禁止的）。请输出 #cf_span[|a|·f(a)] 的最大可能值。 ## Input 第一行包含一个整数 #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] 是禁止的（否则不是禁止的）。 ## Output 请输出 #cf_span[|a|·f(a)] 的最大可能值。 [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the length of string $ s $. Let $ s \in \Sigma^n $, where $ \Sigma = \{a, b, \dots, z\} $, be the input string. Let $ t \in \{0,1\}^n $ be the forbidden indices array: $ t[i] = 1 $ iff index $ i $ (1-based) is forbidden. For any non-empty substring $ a $ of $ s $, define: - $ |a| $: length of $ a $, - $ f(a) $: number of occurrences of $ a $ in $ s $ that end at a non-forbidden index. An occurrence of $ a $ starting at position $ i $ (1-based) ends at position $ i + |a| - 1 $. Thus, $ 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| $. **Constraints** 1. $ 1 \leq n \leq 200000 $ 2. $ s $ consists of lowercase Latin letters. 3. $ t $ consists of characters '0' and '1'. **Objective** Maximize $ |a| \cdot f(a) $ over all non-empty substrings $ a $ of $ s $: $$ \max_{\substack{a \text{ is a substring of } s \\ a \neq \varepsilon}} \left( |a| \cdot f(a) \right) $$

Samples

Input #1

5
ababa
00100

Output #1

Input #2

5
ababa
00000

Output #2

Input #3

5
ababa
11111

Output #3

API Response (JSON)

{
  "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 max...",
      "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_sp...",
      "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 forbi...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments