C. Beaver

Codeforces

IDCF79C

Time2000ms

Memory256MB

Difficulty—

data structuresdpgreedyhashingstringstwo pointers

English · Original

Chinese · Translation

Formal · Original

After Fox Ciel got off a bus, she found that the bus she was on was a wrong bus and she lost her way in a strange town. However, she fortunately met her friend Beaver Taro and asked which way to go to her castle. Taro's response to her was a string _s_, and she tried to remember the string _s_ correctly. However, Ciel feels _n_ strings _b_1, _b_2, ... , _b__n_ are really boring, and unfortunately she dislikes to remember a string that contains a boring substring. To make the thing worse, what she can remember is only the contiguous substring of _s_. Determine the longest contiguous substring of _s_ that does not contain any boring string, so that she can remember the longest part of Taro's response. ## Input In the first line there is a string _s_. The length of _s_ will be between 1 and 105, inclusive. In the second line there is a single integer _n_ (1 ≤ _n_ ≤ 10). Next _n_ lines, there is a string _b__i_ (1 ≤ _i_ ≤ _n_). Each length of _b__i_ will be between 1 and 10, inclusive. Each character of the given strings will be either a English alphabet (both lowercase and uppercase) or a underscore (_'_'_) or a digit. Assume that these strings are case-sensitive. ## Output Output in the first line two space-separated integers _len_ and _pos_: the length of the longest contiguous substring of _s_ that does not contain any _b__i_, and the first position of the substring (0-indexed). The position _pos_ must be between 0 and |_s_| - _len_ inclusive, where |_s_| is the length of string _s_. If there are several solutions, output any. [samples] ## Note In the first sample, the solution is _traight_alon_. In the second sample, the solution is an empty string, so the output can be «_0 0_», «_0 1_», «_0 2_», and so on. In the third sample, the solution is either _nagio_ or _oisii_.

在狐狸Ciel下公交车后，她发现她乘坐的公交车坐错了，迷失在一个陌生的城镇中。然而，她幸运地遇到了她的朋友海狸Taro，并询问去她城堡的路。Taro对她的回应是一个字符串 #cf_span[s]，她试图正确记住这个字符串 #cf_span[s]。然而，Ciel觉得 #cf_span[n] 个字符串 #cf_span[b1, b2, ... , bn] 非常无聊，不幸的是，她不喜欢记住包含任何无聊子串的字符串。更糟糕的是，她只能记住 #cf_span[s] 的连续子串。请确定 #cf_span[s] 中最长的不包含任何无聊字符串的连续子串，以便她能记住Taro回应的最长部分。第一行包含一个字符串 #cf_span[s]。#cf_span[s] 的长度在 #cf_span[1] 到 #cf_span[105] 之间（包含两端）。第二行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 10]）。接下来的 #cf_span[n] 行，每行包含一个字符串 #cf_span[bi]（#cf_span[1 ≤ i ≤ n]）。每个 #cf_span[bi] 的长度在 #cf_span[1] 到 #cf_span[10] 之间（包含两端）。给定字符串中的每个字符均为英文字母（大小写均可）、下划线（_）或数字。假设这些字符串区分大小写。请在第一行输出两个用空格分隔的整数 #cf_span[len] 和 #cf_span[pos]：表示 #cf_span[s] 中最长的不包含任何 #cf_span[bi] 的连续子串的长度，以及该子串的起始位置（0索引）。位置 #cf_span[pos] 必须满足 #cf_span[0 ≤ pos ≤ |s| - len]，其中 #cf_span[|s|] 是字符串 #cf_span[s] 的长度。如果有多个解，输出任意一个即可。在第一个样例中，解为 _traight_alon_。在第二个样例中，解为空字符串，因此输出可以是 «_0 0_»、«_0 1_»、«_0 2_» 等等。在第三个样例中，解为 _nagio_ 或 _oisii_ 之一。 ## Input 第一行包含一个字符串 #cf_span[s]。#cf_span[s] 的长度在 #cf_span[1] 到 #cf_span[105] 之间（包含两端）。第二行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 10]）。接下来的 #cf_span[n] 行，每行包含一个字符串 #cf_span[bi]（#cf_span[1 ≤ i ≤ n]）。每个 #cf_span[bi] 的长度在 #cf_span[1] 到 #cf_span[10] 之间（包含两端）。给定字符串中的每个字符均为英文字母（大小写均可）、下划线（_）或数字。假设这些字符串区分大小写。 ## Output 请在第一行输出两个用空格分隔的整数 #cf_span[len] 和 #cf_span[pos]：表示 #cf_span[s] 中最长的不包含任何 #cf_span[bi] 的连续子串的长度，以及该子串的起始位置（0索引）。位置 #cf_span[pos] 必须满足 #cf_span[0 ≤ pos ≤ |s| - len]，其中 #cf_span[|s|] 是字符串 #cf_span[s] 的长度。如果有多个解，输出任意一个即可。 [samples] ## Note 在第一个样例中，解为 _traight_alon_。在第二个样例中，解为空字符串，因此输出可以是 «_0 0_»、«_0 1_»、«_0 2_» 等等。在第三个样例中，解为 _nagio_ 或 _oisii_ 之一。

**Definitions** Let $ s \in \Sigma^* $ be the target string, where $ \Sigma = \{ \text{a-z, A-Z, _, 0-9} \} $. Let $ B = \{ b_1, b_2, \dots, b_n \} \subseteq \Sigma^* $ be the set of "boring" substrings, with $ n \leq 10 $, and $ |b_i| \leq 10 $ for all $ i $. **Constraints** 1. $ 1 \leq |s| \leq 10^5 $ 2. $ 1 \leq n \leq 10 $ 3. $ 1 \leq |b_i| \leq 10 $ for all $ b_i \in B $ 4. All strings are case-sensitive. **Objective** Find a contiguous substring $ s[i:j] $ (with $ 0 \leq i \leq j \leq |s| $) such that: - $ s[i:j] $ contains **no** substring equal to any $ b_k \in B $, - $ j - i $ is maximized, - Output the pair $ (\text{len}, \text{pos}) = (j - i, i) $. If multiple such substrings exist with maximum length, output any.

Samples

Input #1

Go_straight_along_this_street
5
str
long
tree
biginteger
ellipse

Output #1

12 4

Input #2

IhaveNoIdea
9
I
h
a
v
e
N
o
I
d

Output #2

0 0

Input #3

unagioisii
2
ioi
unagi

Output #3

5 5

API Response (JSON)

{
  "problem": {
    "name": "C. Beaver",
    "description": {
      "content": "After Fox Ciel got off a bus, she found that the bus she was on was a wrong bus and she lost her way in a strange town. However, she fortunately met her friend Beaver Taro and asked which way to go to",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF79C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "After Fox Ciel got off a bus, she found that the bus she was on was a wrong bus and she lost her way in a strange town. However, she fortunately met her friend Beaver Taro and asked which way to go to...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "在狐狸Ciel下公交车后，她发现她乘坐的公交车坐错了，迷失在一个陌生的城镇中。然而，她幸运地遇到了她的朋友海狸Taro，并询问去她城堡的路。Taro对她的回应是一个字符串 #cf_span[s]，她试图正确记住这个字符串 #cf_span[s]。\n\n然而，Ciel觉得 #cf_span[n] 个字符串 #cf_span[b1, b2, ... , bn] 非常无聊，不幸的是，她不喜欢记住包含任何无...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\Sigma^* $ be the target string, where $ \\Sigma = \\{ \\text{a-z, A-Z, _, 0-9} \\} $.  \nLet $ B = \\{ b_1, b_2, \\dots, b_n \\} \\subseteq \\Sigma^* $ be the set of \"boring\" subs...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments