{"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 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.\n\nSubsequence of string _s_ is any such string that can be obtained by erasing zero or more characters (**not necessarily consecutive**) from string _s_.\n\n## Input\n\nThe 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.\n\n## Output\n\nOn the first line output a subsequence of string _a_, obtained from _b_ by erasing the minimum number of consecutive characters.\n\nIf the answer consists of zero characters, output «_\\-_» (a minus sign).\n\n[samples]\n\n## Note\n\nIn the first example strings _a_ and _b_ don't share any symbols, so the longest string that you can get is empty.\n\nIn 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_.","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] 中删除零个或多个字符（不一定是连续的）所得到的任意字符串。\n\n第一行包含字符串 #cf_span[a]，第二行包含字符串 #cf_span[b]。这两个字符串均非空，且仅由英文小写字母组成，每个字符串的长度不超过 #cf_span[105] 个字符。\n\n在第一行输出一个子序列，该子序列由从 #cf_span[b] 中移除最少数量的连续字符后得到。\n\n如果答案为空字符串，请输出 «_-_»（一个减号）。 \n\n在第一个例子中，字符串 #cf_span[a] 和 #cf_span[b] 没有共同的字符，因此你能得到的最长字符串是空的。\n\n在第二个例子中，_ac_ 是 #cf_span[a] 的子序列，同时你也可以通过从 #cf_span[b] 中移除连续字符 _cepted_ 来得到它。\n\n## Input\n\n第一行包含字符串 #cf_span[a]，第二行包含字符串 #cf_span[b]。这两个字符串均非空，且仅由英文小写字母组成，每个字符串的长度不超过 #cf_span[105] 个字符。\n\n## Output\n\n在第一行输出一个子序列，该子序列由从 #cf_span[b] 中移除最少数量的连续字符后得到。如果答案为空字符串，请输出 «_-_»（一个减号）。\n\n[samples]\n\n## Note\n\n在第一个例子中，字符串 #cf_span[a] 和 #cf_span[b] 没有共同的字符，因此你能得到的最长字符串是空的。在第二个例子中，_ac_ 是 #cf_span[a] 的子序列，同时你也可以通过从 #cf_span[b] 中移除连续字符 _cepted_ 来得到它。","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 of $ a $.  \n\n**Constraints**  \n1. $ 1 \\leq |a|, |b| \\leq 10^5 $  \n2. All characters in $ a $ and $ b $ are lowercase English letters.  \n\n**Objective**  \nFind a substring $ b' $ of $ b $ (i.e., $ b' = b[i:j] $ for some $ 0 \\leq i \\leq j \\leq |b| $) such that:  \n- $ b' \\in \\text{subseq}(a) $, and  \n- $ |b'| $ is maximized.  \n\nLet $ b^* $ be such a substring of maximum length.  \n\n**Output**  \n- If $ |b^*| = 0 $, output `_`  \n- Otherwise, output $ b^* $","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF762C","tags":["binary search","hashing","strings","two pointers"],"sample_group":[["hi\nbob","\\-"],["abca\naccepted","ac"],["abacaba\nabcdcba","abcba"]],"created_at":"2026-03-03 11:00:39"}}