E. Rusty String

Codeforces

IDCF827E

Time3000ms

Memory512MB

Difficulty—

fftmathstrings

English · Original

Chinese · Translation

Formal · Original

Grigory loves strings. Recently he found a metal strip on a loft. The strip had length _n_ and consisted of letters "_V_" and "_K_". Unfortunately, rust has eaten some of the letters so that it's now impossible to understand which letter was written. Grigory couldn't understand for a long time what these letters remind him of, so he became interested in the following question: if we put a letter "_V_" or "_K_" on each unreadable position, which values can the period of the resulting string be equal to? A period of a string is such an integer _d_ from 1 to the length of the string that if we put the string shifted by _d_ positions to the right on itself, then all overlapping letters coincide. For example, 3 and 5 are periods of "_VKKVK_". ## Input There are several (at least one) test cases in the input. The first line contains single integer — the number of test cases. There is an empty line before each test case. Each test case is described in two lines: the first line contains single integer _n_ (1 ≤ _n_ ≤ 5·105) — the length of the string, the second line contains the string of length _n_, consisting of letters "_V_", "_K_" and characters "_?_". The latter means the letter on its position is unreadable. It is guaranteed that the sum of lengths among all test cases doesn't exceed 5·105. **For hacks** you can only use tests with one test case. ## Output For each test case print two lines. In the first line print the number of possible periods after we replace each unreadable letter with "_V_" or "_K_". In the next line print all these values in increasing order. [samples] ## Note In the first test case from example we can obtain, for example, "_VKKVK_", which has periods 3 and 5. In the second test case we can obtain "_VVVVVV_" which has all periods from 1 to 6. In the third test case string "_KVKV_" has periods 2 and 4, and string "_KVKK_" has periods 3 and 4.

Grigory 爱好字符串。最近他在阁楼上发现了一条金属条，其长度为 $n$，由字母 "V" 和 "K" 组成。不幸的是，锈蚀破坏了一些字母，导致现在无法辨认原本写的是哪个字母。 Grigory 长时间思考这些字母让他想起了什么，于是他产生了如下问题：如果我们在每个不可读的位置填入一个 "V" 或 "K"，那么所得字符串的周期可能取哪些值？一个字符串的周期是一个整数 $d$（$1 \leq d \leq $ 字符串长度），满足将字符串向右平移 $d$ 个位置后与原字符串重叠的部分，所有重叠位置的字母完全一致。例如，$3$ 和 $5$ 都是字符串 "VKKVK" 的周期。输入包含多个（至少一个）测试用例。第一行包含一个整数——测试用例的数量。每个测试用例前有一行空行。每个测试用例由两行描述：第一行包含一个整数 $n$（$1 \leq n \leq 5\cdot10^5$）——字符串的长度；第二行包含一个长度为 $n$ 的字符串，由字母 "V"、"K" 和字符 "?" 组成，其中 "?" 表示该位置的字母不可读。保证所有测试用例的长度总和不超过 $5\cdot10^5$。 *对于黑客测试*，你只能使用只有一个测试用例的输入。对于每个测试用例，输出两行。第一行输出在将每个不可读字母替换为 "V" 或 "K" 后，可能的周期值的个数；第二行按升序输出所有这些周期值。 ## Input There are several (at least one) test cases in the input. The first line contains single integer — the number of test cases.There is an empty line before each test case. Each test case is described in two lines: the first line contains single integer $n$ ($1 \leq n \leq 5\cdot10^5$) — the length of the string, the second line contains the string of length $n$, consisting of letters "V", "K" and characters "?". The latter means the letter on its position is unreadable.It is guaranteed that the sum of lengths among all test cases doesn't exceed $5\cdot10^5$.*For hacks* you can only use tests with one test case. ## Output For each test case print two lines. In the first line print the number of possible periods after we replace each unreadable letter with "V" or "K". In the next line print all these values in increasing order. [samples] ## Note 在第一个示例测试用例中，我们可以得到例如 "VKKVK"，它具有周期 $3$ 和 $5$。在第二个测试用例中，我们可以得到 "VVVVVV"，它具有从 $1$ 到 $6$ 的所有周期。在第三个测试用例中，字符串 "KVKV" 具有周期 $2$ 和 $4$，字符串 "KVKK" 具有周期 $3$ 和 $4$。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the length of the string. Let $ S \in (\{V, K, ?\})^n $ be the input string, where $ ? $ denotes an unreadable character. Let $ \mathcal{A} $ be the set of all strings $ A \in \{V, K\}^n $ such that $ A[i] = S[i] $ for all $ i $ where $ S[i] \neq ? $. Let $ d \in \{1, 2, \dots, n\} $ be a candidate period. $ d $ is a period of string $ A $ if and only if $ A[i] = A[i + d] $ for all $ i \in \{1, \dots, n - d\} $. **Constraints** 1. $ 1 \leq n \leq 5 \cdot 10^5 $ 2. The total sum of $ n $ across all test cases $ \leq 5 \cdot 10^5 $ 3. At least one assignment exists (i.e., $ \mathcal{A} \neq \emptyset $) **Objective** For each test case, compute the set $ P \subseteq \{1, 2, \dots, n\} $ such that: $$ P = \left\{ d \in \{1, \dots, n\} \mid \exists A \in \mathcal{A} \text{ such that } A[i] = A[i + d] \text{ for all } i = 1, \dots, n - d \right\} $$ Output $ |P| $ and the elements of $ P $ in increasing order.

Samples

Input #1

3
 
5
V??VK
 
6
??????
 
4
?VK?

Output #1

2
3 5
6
1 2 3 4 5 6
3
2 3 4

API Response (JSON)

{
  "problem": {
    "name": "E. Rusty String",
    "description": {
      "content": "Grigory loves strings. Recently he found a metal strip on a loft. The strip had length _n_ and consisted of letters \"_V_\" and \"_K_\". Unfortunately, rust has eaten some of the letters so that it's now ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF827E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Grigory loves strings. Recently he found a metal strip on a loft. The strip had length _n_ and consisted of letters \"_V_\" and \"_K_\". Unfortunately, rust has eaten some of the letters so that it's now ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Grigory 爱好字符串。最近他在阁楼上发现了一条金属条，其长度为 $n$，由字母 \"V\" 和 \"K\" 组成。不幸的是，锈蚀破坏了一些字母，导致现在无法辨认原本写的是哪个字母。\n\nGrigory 长时间思考这些字母让他想起了什么，于是他产生了如下问题：如果我们在每个不可读的位置填入一个 \"V\" 或 \"K\"，那么所得字符串的周期可能取哪些值？\n\n一个字符串的周期是一个整数 $d$（$1 \\leq ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the string.  \nLet $ S \\in (\\{V, K, ?\\})^n $ be the input string, where $ ? $ denotes an unreadable character.  \nLet $ \\mathcal{A} $ be the...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments