D. Frequency of String

Codeforces

IDCF963D

Time1000ms

Memory512MB

Difficulty—

hashingstring suffix structuresstrings

English · Original

Chinese · Translation

Formal · Original

You are given a string $s$. You should answer $n$ queries. The $i$\-th query consists of integer $k_i$ and string $m_i$. The answer for this query is the minimum length of such a string $t$ that $t$ is a substring of $s$ and $m_i$ has at least $k_i$ occurrences as a substring in $t$. A substring of a string is a continuous segment of characters of the string. It is guaranteed that for any two queries the strings $m_i$ from these queries are different. ## Input The first line contains string $s$ $(1 \leq \left | s \right | \leq 10^{5})$. The second line contains an integer $n$ ($1 \leq n \leq 10^5$). Each of next $n$ lines contains an integer $k_i$ $(1 \leq k_i \leq |s|)$ and a non-empty string $m_i$ — parameters of the query with number $i$, in this order. All strings in input consists of lowercase English letters. Sum of length of all strings in input doesn't exceed $10^5$. All $m_i$ are distinct. ## Output For each query output the answer for it in a separate line. If a string $m_{i}$ occurs in $s$ less that $k_{i}$ times, output _\-1_. [samples]

给定一个字符串 $s$。你需要回答 $n$ 个查询。第 $i$ 个查询由整数 $k_i$ 和字符串 $m_i$ 组成。该查询的答案是满足以下条件的最短字符串 $t$ 的长度：$t$ 是 $s$ 的子串，且 $m_i$ 在 $t$ 中作为子串至少出现 $k_i$ 次。字符串的子串是指该字符串中连续的一段字符。保证任意两个查询中的字符串 $m_i$ 都不相同。第一行包含字符串 $s$ $(1 lt.eq | s | lt.eq 10^5)$。第二行包含一个整数 $n$ ($1 lt.eq n lt.eq 10^5$)。接下来的 $n$ 行中，每行包含一个整数 $k_i$ $(1 lt.eq k_i lt.eq | s |)$ 和一个非空字符串 $m_i$ —— 第 $i$ 个查询的参数，按此顺序给出。输入中的所有字符串均由小写英文字母组成。输入中所有字符串的长度之和不超过 $10^5$。所有 $m_i$ 互不相同。对于每个查询，在单独一行中输出其答案。如果字符串 $m_i$ 在 $s$ 中出现的次数少于 $k_i$ 次，则输出 _-1_。 ## Input 第一行包含字符串 $s$ $(1 lt.eq | s | lt.eq 10^5)$。第二行包含一个整数 $n$ ($1 lt.eq n lt.eq 10^5$)。接下来的 $n$ 行中，每行包含一个整数 $k_i$ $(1 lt.eq k_i lt.eq | s |)$ 和一个非空字符串 $m_i$ —— 第 $i$ 个查询的参数，按此顺序给出。输入中的所有字符串均由小写英文字母组成。输入中所有字符串的长度之和不超过 $10^5$。所有 $m_i$ 互不相同。 ## Output 对于每个查询，在单独一行中输出其答案。如果字符串 $m_i$ 在 $s$ 中出现的次数少于 $k_i$ 次，则输出 _-1_。 [samples]

**Definitions** Let $ s \in \Sigma^* $ be the input string, where $ \Sigma $ is the set of lowercase English letters. Let $ n \in \mathbb{Z}^+ $ be the number of queries. For each query $ i \in \{1, \dots, n\} $, let $ k_i \in \mathbb{Z}^+ $ and $ m_i \in \Sigma^* \setminus \{\varepsilon\} $ be the query parameters, with all $ m_i $ distinct. Let $ \text{occ}_s(m) $ denote the number of occurrences of substring $ m $ in $ s $, counted with overlap. **Constraints** 1. $ 1 \le |s| \le 10^5 $ 2. $ 1 \le n \le 10^5 $ 3. For each $ i $, $ 1 \le k_i \le |s| $ 4. All $ m_i $ are non-empty and distinct 5. $ \sum_{i=1}^n |m_i| \le 10^5 $ **Objective** For each query $ i $: - If $ \text{occ}_s(m_i) < k_i $, output $ -1 $. - Otherwise, compute: $$ \min \left\{ |t| \;\middle|\; t \text{ is a substring of } s \text{ and } \text{occ}_t(m_i) \ge k_i \right\} $$

Samples

Input #1

aaaaa
5
3 a
3 aa
2 aaa
3 aaaa
1 aaaaa

Output #1

Input #2

abbb
7
4 b
1 ab
3 bb
1 abb
2 bbb
1 a
2 abbb

Output #2

\-1
2
-1
3
-1
1
-1

API Response (JSON)

{
  "problem": {
    "name": "D. Frequency of String",
    "description": {
      "content": "You are given a string $s$. You should answer $n$ queries. The $i$\\-th query consists of integer $k_i$ and string $m_i$. The answer for this query is the minimum length of such a string $t$ that $t$ i",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF963D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a string $s$. You should answer $n$ queries. The $i$\\-th query consists of integer $k_i$ and string $m_i$. The answer for this query is the minimum length of such a string $t$ that $t$ i...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定一个字符串 $s$。你需要回答 $n$ 个查询。第 $i$ 个查询由整数 $k_i$ 和字符串 $m_i$ 组成。该查询的答案是满足以下条件的最短字符串 $t$ 的长度：$t$ 是 $s$ 的子串，且 $m_i$ 在 $t$ 中作为子串至少出现 $k_i$ 次。\n\n字符串的子串是指该字符串中连续的一段字符。\n\n保证任意两个查询中的字符串 $m_i$ 都不相同。\n\n第一行包含字符串 $s$ $(...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\Sigma^* $ be the input string, where $ \\Sigma $ is the set of lowercase English letters.  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of queries.  \nFor each query $ i \\in ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments