D. String Game

Codeforces

IDCF779D

Time2000ms

Memory512MB

Difficulty—

binary searchstrings

English · Original

Chinese · Translation

Formal · Original

Little Nastya has a hobby, she likes to remove some letters from word, to obtain another word. But it turns out to be pretty hard for her, because she is too young. Therefore, her brother Sergey always helps her. Sergey gives Nastya the word _t_ and wants to get the word _p_ out of it. Nastya removes letters in a certain order (one after another, in this order strictly), which is specified by permutation of letters' indices of the word _t_: _a_1... _a_|_t_|. We denote the length of word _x_ as |_x_|. Note that after removing one letter, the indices of other letters don't change. For example, if _t_ = "_nastya_" and _a_ = \[4, 1, 5, 3, 2, 6\] then removals make the following sequence of words "_nastya_" "_nastya_" "_nastya_" "_nastya_" "_nastya_" "_nastya_" "_nastya_". Sergey knows this permutation. His goal is to stop his sister at some point and continue removing by himself to get the word _p_. Since Nastya likes this activity, Sergey wants to stop her as late as possible. Your task is to determine, how many letters Nastya can remove before she will be stopped by Sergey. It is guaranteed that the word _p_ can be obtained by removing the letters from word _t_. ## Input The first and second lines of the input contain the words _t_ and _p_, respectively. Words are composed of lowercase letters of the Latin alphabet (1 ≤ |_p_| < |_t_| ≤ 200 000). It is guaranteed that the word _p_ can be obtained by removing the letters from word _t_. Next line contains a permutation _a_1, _a_2, ..., _a_|_t_| of letter indices that specifies the order in which Nastya removes letters of _t_ (1 ≤ _a__i_ ≤ |_t_|, all _a__i_ are distinct). ## Output Print a single integer number, the maximum number of letters that Nastya can remove. [samples] ## Note In the first sample test sequence of removing made by Nastya looks like this: "_ababcba_" "_ababcba_" "_ababcba_" "_ababcba_" Nastya can not continue, because it is impossible to get word "_abb_" from word "_ababcba_". So, Nastya will remove only three letters.

小娜斯娅有一个爱好，她喜欢从一个单词中删除一些字母，以得到另一个单词。但对她来说这相当困难，因为她太年轻了。因此，她的哥哥谢尔盖总是帮助她。谢尔盖给娜斯娅一个单词 #cf_span[t]，并希望从中得到单词 #cf_span[p]。娜斯娅按照特定的顺序（逐个删除，顺序严格）删除字母，这个顺序由单词 #cf_span[t] 的字母索引的一个排列指定：#cf_span[a1... a|t|]。我们用 #cf_span[|x|] 表示单词 #cf_span[x] 的长度。注意，删除一个字母后，其他字母的索引不会改变。例如，如果 #cf_span[t = ]"_nastya_" 且 #cf_span[a = [4, 1, 5, 3, 2, 6]]，则删除操作会依次产生以下单词序列："_nastya_" → "_nastya_" → "_nastya_" → "_nastya_" → "_nastya_" → "_nastya_" → "_nastya_"。谢尔盖知道这个排列。他的目标是在某个时刻阻止妹妹，然后自己继续删除，以得到单词 #cf_span[p]。由于娜斯娅喜欢这个活动，谢尔盖希望尽可能晚地阻止她。你的任务是确定娜斯娅在被谢尔盖阻止前最多能删除多少个字母。保证单词 #cf_span[p] 可以通过从单词 #cf_span[t] 中删除字母得到。输入的第一行和第二行分别包含单词 #cf_span[t] 和 #cf_span[p]。单词由拉丁字母的小写字母组成（#cf_span[1 ≤ |p| < |t| ≤ 200 000]）。保证单词 #cf_span[p] 可以通过从单词 #cf_span[t] 中删除字母得到。下一行包含一个排列 #cf_span[a1, a2, ..., a|t|]，表示娜斯娅删除单词 #cf_span[t] 中字母的顺序（#cf_span[1 ≤ ai ≤ |t|]，所有 #cf_span[ai] 互不相同）。请输出一个整数，表示娜斯娅最多可以删除的字母数量。在第一个样例中，娜斯娅的删除序列如下： "_ababcba_" → "_ababcba_" → "_ababcba_" → "_ababcba_" 娜斯娅无法继续，因为无法从单词 "_ababcba_" 中得到单词 "_abb_"。因此，娜斯娅只能删除三个字母。 ## Input 输入的第一行和第二行分别包含单词 #cf_span[t] 和 #cf_span[p]。单词由拉丁字母的小写字母组成（#cf_span[1 ≤ |p| < |t| ≤ 200 000]）。保证单词 #cf_span[p] 可以通过从单词 #cf_span[t] 中删除字母得到。下一行包含一个排列 #cf_span[a1, a2, ..., a|t|]，表示娜斯娅删除单词 #cf_span[t] 中字母的顺序（#cf_span[1 ≤ ai ≤ |t|]，所有 #cf_span[ai] 互不相同）。 ## Output 请输出一个整数，表示娜斯娅最多可以删除的字母数量。 [samples] ## Note 在第一个样例中，娜斯娅的删除序列如下："_ababcba_" → "_ababcba_" → "_ababcba_" → "_ababcba_"。娜斯娅无法继续，因为无法从单词 "_ababcba_" 中得到单词 "_abb_"。因此，娜斯娅只能删除三个字母。

**Definitions** Let $ t \in \Sigma^* $ be the initial word, $ p \in \Sigma^* $ be the target word, with $ |p| < |t| $. Let $ A = (a_1, a_2, \dots, a_{|t|}) $ be a permutation of indices $ \{1, 2, \dots, |t|\} $, specifying the order of letter removals. Let $ t^{(k)} $ denote the word obtained after removing the first $ k $ letters according to $ A $, i.e., removing indices $ a_1, a_2, \dots, a_k $ from $ t $. **Constraints** 1. $ 1 \leq |p| < |t| \leq 200{,}000 $ 2. $ p $ is a subsequence of $ t $ 3. All $ a_i \in \{1, 2, \dots, |t|\} $ are distinct **Objective** Find the maximum $ k \in \{0, 1, \dots, |t| - |p|\} $ such that $ p $ is a subsequence of $ t^{(k)} $.

Samples

Input #1

ababcba
abb
5 3 4 1 7 6 2

Output #1

Input #2

bbbabb
bb
1 6 3 4 2 5

Output #2

API Response (JSON)

{
  "problem": {
    "name": "D. String Game",
    "description": {
      "content": "Little Nastya has a hobby, she likes to remove some letters from word, to obtain another word. But it turns out to be pretty hard for her, because she is too young. Therefore, her brother Sergey alway",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF779D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Little Nastya has a hobby, she likes to remove some letters from word, to obtain another word. But it turns out to be pretty hard for her, because she is too young. Therefore, her brother Sergey alway...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "小娜斯娅有一个爱好，她喜欢从一个单词中删除一些字母，以得到另一个单词。但对她来说这相当困难，因为她太年轻了。因此，她的哥哥谢尔盖总是帮助她。\n\n谢尔盖给娜斯娅一个单词 #cf_span[t]，并希望从中得到单词 #cf_span[p]。娜斯娅按照特定的顺序（逐个删除，顺序严格）删除字母，这个顺序由单词 #cf_span[t] 的字母索引的一个排列指定：#cf_span[a1... a|t|]。我们...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ t \\in \\Sigma^* $ be the initial word, $ p \\in \\Sigma^* $ be the target word, with $ |p| < |t| $.  \nLet $ A = (a_1, a_2, \\dots, a_{|t|}) $ be a permutation of indices $ \\{1, 2, ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments