codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1989B.md (1823B)


      1 Source: https://codeforces.com/problemset/problem/1989/B
      2 
      3 B. Substring and Subsequence
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given two strings $a$ and $b$, both consisting of lowercase Latin letters.
     22 
     23 A subsequence of a string is a string which can be obtained by removing several (possibly zero) characters from the original string. A substring of a string is a contiguous subsequence of that string.
     24 
     25 For example, consider the string abac:
     26 
     27 * a, b, c, ab, aa, ac, ba, bc, aba, abc, aac, bac and abac are its subsequences;
     28 * a, b, c, ab, ba, ac, aba, bac and abac are its substrings.
     29 
     30 Your task is to calculate the minimum possible length of the string that contains $a$ as a substring and $b$ as a subsequence.
     31 
     32 Input
     33 
     34 The first line contains a single integer $t$ ($1 \le t \le 10^3$) — the number of test cases.
     35 
     36 The first line of each test case contains a string $a$ ($1 \le |a| \le 100$), consisting of lowercase Latin letters.
     37 
     38 The second line of each test case contains a string $b$ ($1 \le |b| \le 100$), consisting of lowercase Latin letters.
     39 
     40 Output
     41 
     42 For each test case, print a single integer — the minimum possible length of the string that contains $a$ as a substring and $b$ as a subsequence.
     43 
     44 Example
     45 
     46 Input
     47 
     48 ```
     49 5
     50 
     51 aba
     52 
     53 cb
     54 
     55 er
     56 
     57 cf
     58 
     59 mmm
     60 
     61 mmm
     62 
     63 contest
     64 
     65 test
     66 
     67 cde
     68 
     69 abcefg
     70 ```
     71 
     72 Output
     73 
     74 ```
     75 4
     76 4
     77 3
     78 7
     79 7
     80 ```
     81 
     82 Note
     83 
     84 In the examples below, the characters that correspond to the subsequence equal to $b$ are bolded.
     85 
     86 In the first example, one of the possible answers is caba.
     87 
     88 In the second example, one of the possible answers is ercf.
     89 
     90 In the third example, one of the possible answers is mmm.
     91 
     92 In the fourth example, one of the possible answers is contest.
     93 
     94 In the fifth example, one of the possible answers is abcdefg.