1506C.md (2275B)
1 Source: https://codeforces.com/problemset/problem/1506/C 2 3 C. Double-ended Strings 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 the strings $a$ and $b$, consisting of lowercase Latin letters. You can do any number of the following operations in any order: 22 23 * if $|a| \gt 0$ (the length of the string $a$ is greater than zero), delete the first character of the string $a$, that is, replace $a$ with $a_2 a_3 \ldots a_n$; 24 * if $|a| \gt 0$, delete the last character of the string $a$, that is, replace $a$ with $a_1 a_2 \ldots a_{n-1}$; 25 * if $|b| \gt 0$ (the length of the string $b$ is greater than zero), delete the first character of the string $b$, that is, replace $b$ with $b_2 b_3 \ldots b_n$; 26 * if $|b| \gt 0$, delete the last character of the string $b$, that is, replace $b$ with $b_1 b_2 \ldots b_{n-1}$. 27 28 Note that after each of the operations, the string $a$ or $b$ may become empty. 29 30 For example, if $a=$"hello" and $b=$"icpc", then you can apply the following sequence of operations: 31 32 * delete the first character of the string $a$ $\Rightarrow$ $a=$"ello" and $b=$"icpc"; 33 * delete the first character of the string $b$ $\Rightarrow$ $a=$"ello" and $b=$"cpc"; 34 * delete the first character of the string $b$ $\Rightarrow$ $a=$"ello" and $b=$"pc"; 35 * delete the last character of the string $a$ $\Rightarrow$ $a=$"ell" and $b=$"pc"; 36 * delete the last character of the string $b$ $\Rightarrow$ $a=$"ell" and $b=$"p". 37 38 For the given strings $a$ and $b$, find the minimum number of operations for which you can make the strings $a$ and $b$ equal. Note that empty strings are also equal. 39 40 Input 41 42 The first line contains a single integer $t$ ($1 \le t \le 100$). Then $t$ test cases follow. 43 44 The first line of each test case contains the string $a$ ($1 \le |a| \le 20$), consisting of lowercase Latin letters. 45 46 The second line of each test case contains the string $b$ ($1 \le |b| \le 20$), consisting of lowercase Latin letters. 47 48 Output 49 50 For each test case, output the minimum number of operations that can make the strings $a$ and $b$ equal. 51 52 Example 53 54 Input 55 56 ``` 57 5 58 a 59 a 60 abcd 61 bc 62 hello 63 codeforces 64 hello 65 helo 66 dhjakjsnasjhfksafasd 67 adjsnasjhfksvdafdser 68 ``` 69 70 Output 71 72 ``` 73 0 74 2 75 13 76 3 77 20 78 ```