C. Two strings

Codeforces

IDCF762C

Time2000ms

Memory256MB

Difficulty—

binary searchhashingstringstwo pointers

English · Original

Chinese · Translation

Formal · Original

You are given two strings _a_ and _b_. You have to remove the minimum possible number of **consecutive** (standing one after another) characters from string _b_ in such a way that it becomes a subsequence of string _a_. It can happen that you will not need to remove any characters at all, or maybe you will have to remove all of the characters from _b_ and make it empty. Subsequence of string _s_ is any such string that can be obtained by erasing zero or more characters (**not necessarily consecutive**) from string _s_. ## Input The first line contains string _a_, and the second line — string _b_. Both of these strings are nonempty and consist of lowercase letters of English alphabet. The length of each string is no bigger than 105 characters. ## Output On the first line output a subsequence of string _a_, obtained from _b_ by erasing the minimum number of consecutive characters. If the answer consists of zero characters, output «_\-_» (a minus sign). [samples] ## Note In the first example strings _a_ and _b_ don't share any symbols, so the longest string that you can get is empty. In the second example _ac_ is a subsequence of _a_, and at the same time you can obtain it by erasing consecutive symbols _cepted_ from string _b_.

给定两个字符串 #cf_span[a] 和 #cf_span[b]。你需要从字符串 #cf_span[b] 中移除尽可能少的*连续*（彼此相邻）字符，使得剩余部分成为字符串 #cf_span[a] 的子序列。可能不需要移除任何字符，也可能需要移除 #cf_span[b] 中的所有字符使其变为空字符串。字符串 #cf_span[s] 的子序列是指通过从 #cf_span[s] 中删除零个或多个字符（不一定是连续的）所得到的任意字符串。第一行包含字符串 #cf_span[a]，第二行包含字符串 #cf_span[b]。这两个字符串均非空，且仅由英文小写字母组成，每个字符串的长度不超过 #cf_span[105] 个字符。在第一行输出一个子序列，该子序列由从 #cf_span[b] 中移除最少数量的连续字符后得到。如果答案为空字符串，请输出 «_-_»（一个减号）。在第一个例子中，字符串 #cf_span[a] 和 #cf_span[b] 没有共同的字符，因此你能得到的最长字符串是空的。在第二个例子中，_ac_ 是 #cf_span[a] 的子序列，同时你也可以通过从 #cf_span[b] 中移除连续字符 _cepted_ 来得到它。 ## Input 第一行包含字符串 #cf_span[a]，第二行包含字符串 #cf_span[b]。这两个字符串均非空，且仅由英文小写字母组成，每个字符串的长度不超过 #cf_span[105] 个字符。 ## Output 在第一行输出一个子序列，该子序列由从 #cf_span[b] 中移除最少数量的连续字符后得到。如果答案为空字符串，请输出 «_-_»（一个减号）。 [samples] ## Note 在第一个例子中，字符串 #cf_span[a] 和 #cf_span[b] 没有共同的字符，因此你能得到的最长字符串是空的。在第二个例子中，_ac_ 是 #cf_span[a] 的子序列，同时你也可以通过从 #cf_span[b] 中移除连续字符 _cepted_ 来得到它。

**Definitions** Let $ a, b \in \Sigma^* $ be two nonempty strings over the alphabet $ \Sigma = \{a, b, \dots, z\} $. Let $ \text{subseq}(a) \subseteq \Sigma^* $ denote the set of all subsequences of $ a $. **Constraints** 1. $ 1 \leq |a|, |b| \leq 10^5 $ 2. All characters in $ a $ and $ b $ are lowercase English letters. **Objective** Find a substring $ b' $ of $ b $ (i.e., $ b' = b[i:j] $ for some $ 0 \leq i \leq j \leq |b| $) such that: - $ b' \in \text{subseq}(a) $, and - $ |b'| $ is maximized. Let $ b^* $ be such a substring of maximum length. **Output** - If $ |b^*| = 0 $, output `_` - Otherwise, output $ b^* $

Samples

Input #1

hi
bob

Output #1

\-

Input #2

abca
accepted

Output #2

ac

Input #3

abacaba
abcdcba

Output #3

abcba

API Response (JSON)

{
  "problem": {
    "name": "C. Two strings",
    "description": {
      "content": "You are given two strings _a_ and _b_. You have to remove the minimum possible number of **consecutive** (standing one after another) characters from string _b_ in such a way that it becomes a subsequ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF762C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given two strings _a_ and _b_. You have to remove the minimum possible number of **consecutive** (standing one after another) characters from string _b_ in such a way that it becomes a subsequ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定两个字符串 #cf_span[a] 和 #cf_span[b]。你需要从字符串 #cf_span[b] 中移除尽可能少的*连续*（彼此相邻）字符，使得剩余部分成为字符串 #cf_span[a] 的子序列。可能不需要移除任何字符，也可能需要移除 #cf_span[b] 中的所有字符使其变为空字符串。\n\n字符串 #cf_span[s] 的子序列是指通过从 #cf_span[s] 中删除零个或多个字...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ a, b \\in \\Sigma^* $ be two nonempty strings over the alphabet $ \\Sigma = \\{a, b, \\dots, z\\} $.  \nLet $ \\text{subseq}(a) \\subseteq \\Sigma^* $ denote the set of all subsequences ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments