C. Newspaper Headline

Codeforces

IDCF92C

Time2000ms

Memory256MB

Difficulty—

binary searchdata structuresdpgreedy

English · Original

Chinese · Translation

Formal · Original

A newspaper is published in Walrusland. Its heading is _s_1, it consists of lowercase Latin letters. Fangy the little walrus wants to buy several such newspapers, cut out their headings, glue them one to another in order to get one big string. After that walrus erase several letters from this string in order to get a new word _s_2. It is considered that when Fangy erases some letter, there's no whitespace formed instead of the letter. That is, the string remains unbroken and it still only consists of lowercase Latin letters. For example, the heading is "_abc_". If we take two such headings and glue them one to the other one, we get "_abcabc_". If we erase the letters on positions 1 and 5, we get a word "_bcac_". Which least number of newspaper headings _s_1 will Fangy need to glue them, erase several letters and get word _s_2? ## Input The input data contain two lines. The first line contain the heading _s_1, the second line contains the word _s_2. The lines only consist of lowercase Latin letters (1 ≤ |_s_1| ≤ 104, 1 ≤ |_s_2| ≤ 106). ## Output If it is impossible to get the word _s_2 in the above-described manner, print "-1" (without the quotes). Otherwise, print the least number of newspaper headings _s_1, which Fangy will need to receive the word _s_2. [samples]

在海狸国发行一份报纸。其报头为 #cf_span[s1]，由小写拉丁字母组成。小海狸 Fangy 想购买若干份这样的报纸，剪下它们的报头，按顺序粘贴在一起，形成一个长字符串。之后，海狸会从这个字符串中擦除若干个字母，以得到一个新的单词 #cf_span[s2]。当 Fangy 擦除某个字母时，不会留下空格，字符串保持连续且仅由小写拉丁字母组成。例如，报头为 "_abc_"。如果我们取两个这样的报头并将其粘贴在一起，会得到 "_abcabc_"。如果我们擦除位置 #cf_span[1] 和 #cf_span[5] 上的字母，会得到单词 "_bcac_"。 Fangy 至少需要多少个报纸报头 #cf_span[s1]，才能通过粘贴、擦除若干字母得到单词 #cf_span[s2]？输入数据包含两行。第一行是报头 #cf_span[s1]，第二行是单词 #cf_span[s2]。这两行仅由小写拉丁字母组成（#cf_span[1 ≤ |s1| ≤ 10^4, 1 ≤ |s2| ≤ 10^6]）。如果无法通过上述方式得到单词 #cf_span[s2]，请输出 "-1"（不含引号）。否则，请输出 Fangy 为获得单词 #cf_span[s2] 所需的最少报纸报头 #cf_span[s1] 的数量。 ## Input 输入数据包含两行。第一行是报头 #cf_span[s1]，第二行是单词 #cf_span[s2]。这两行仅由小写拉丁字母组成（#cf_span[1 ≤ |s1| ≤ 10^4, 1 ≤ |s2| ≤ 10^6]）。 ## Output 如果无法通过上述方式得到单词 #cf_span[s2]，请输出 "-1"（不含引号）。否则，请输出 Fangy 为获得单词 #cf_span[s2] 所需的最少报纸报头 #cf_span[s1] 的数量。 [samples]

Let $ s_1 $ and $ s_2 $ be two strings over the alphabet of lowercase Latin letters. **Definition:** Let $ n = |s_1| $, $ m = |s_2| $. **Constraint:** For each character $ c \in s_2 $, $ c $ must appear in $ s_1 $. Otherwise, output $-1$. **Objective:** Find the minimum number $ k \in \mathbb{N} $ such that $ s_2 $ is a subsequence of $ s_1^k $ (i.e., the concatenation of $ s_1 $ repeated $ k $ times). **Algorithmic formulation:** Traverse $ s_2 $ character by character. For each character $ s_2[i] $, find its next occurrence in $ s_1 $ starting from the current position within a cyclic scan of $ s_1 $. - Initialize $ k = 1 $, and $ pos = -1 $ (current position in the current copy of $ s_1 $). - For each $ c \in s_2 $: - Find the smallest index $ j > pos $ in $ s_1 $ such that $ s_1[j] = c $. - If such $ j $ exists: set $ pos = j $. - Else: increment $ k $, set $ pos = $ index of first occurrence of $ c $ in $ s_1 $. - Return $ k $. **Formal output:** $$ \boxed{ \begin{cases} \text{minimum } k \in \mathbb{N} \text{ such that } s_2 \text{ is a subsequence of } s_1^k, & \text{if } \forall c \in s_2,\ c \in s_1 \\ -1, & \text{otherwise} \end{cases} } $$

Samples

Input #1

abc
xyz

Output #1

\-1

Input #2

abcd
dabc

Output #2

API Response (JSON)

{
  "problem": {
    "name": "C. Newspaper Headline",
    "description": {
      "content": "A newspaper is published in Walrusland. Its heading is _s_1, it consists of lowercase Latin letters. Fangy the little walrus wants to buy several such newspapers, cut out their headings, glue them one",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF92C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A newspaper is published in Walrusland. Its heading is _s_1, it consists of lowercase Latin letters. Fangy the little walrus wants to buy several such newspapers, cut out their headings, glue them one...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "在海狸国发行一份报纸。其报头为 #cf_span[s1]，由小写拉丁字母组成。小海狸 Fangy 想购买若干份这样的报纸，剪下它们的报头，按顺序粘贴在一起，形成一个长字符串。之后，海狸会从这个字符串中擦除若干个字母，以得到一个新的单词 #cf_span[s2]。当 Fangy 擦除某个字母时，不会留下空格，字符串保持连续且仅由小写拉丁字母组成。\n\n例如，报头为 \"_abc_\"。如果我们取两个这样的...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ s_1 $ and $ s_2 $ be two strings over the alphabet of lowercase Latin letters.\n\n**Definition:**  \nLet $ n = |s_1| $, $ m = |s_2| $.\n\n**Constraint:**  \nFor each character $ c \\in s_2 $, $ c $ mus...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments