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.