2050E.md (2279B)
1 Source: https://codeforces.com/problemset/problem/2050/E 2 3 E. Three Strings 4 5 time limit per test 6 7 2.5 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 three strings: $a$, $b$, and $c$, consisting of lowercase Latin letters. The string $c$ was obtained in the following way: 22 23 1. At each step, either string $a$ or string $b$ was randomly chosen, and the first character of the chosen string was removed from it and appended to the end of string $c$, until one of the strings ran out. After that, the remaining characters of the non-empty string were added to the end of $c$. 24 2. Then, a certain number of characters in string $c$ were randomly changed. 25 26 For example, from the strings $a=\color{red}{\text{abra}}$ and $b=\color{blue}{\text{cada}}$, without character replacements, the strings $\color{blue}{\text{ca}}\color{red}{\text{ab}}\color{blue}{\text{d}}\color{red}{\text{ra}}\color{blue}{\text{a}}$, $\color{red}{\text{abra}}\color{blue}{\text{cada}}$, $\color{red}{\text{a}}\color{blue}{\text{cada}}\color{red}{\text{bra}}$ could be obtained. 27 28 Find the minimum number of characters that could have been changed in string $c$. 29 30 Input 31 32 The first line of the input contains a single integer $t$ ($1 \le t \le 10^3$) — the number of test cases. 33 34 The first line of each test case contains one string of lowercase Latin letters $a$ ($1 \leq |a| \leq 10^3$) — the first string, where $|a|$ denotes the length of string $a$. 35 36 The second line of each test case contains one string of lowercase Latin letters $b$ ($1 \leq |b| \leq 10^3$) — the second string, where $|b|$ denotes the length of string $b$. 37 38 The third line of each test case contains one string of lowercase Latin letters $c$ ($|c| = |a| + |b|$) — the third string. 39 40 It is guaranteed that the sum of $|a|$ across all test cases does not exceed $2 \cdot 10^3$. Also, the sum of $|b|$ across all test cases does not exceed $2 \cdot 10^3$. 41 42 Output 43 44 For each test case, output a single integer — the minimum number of characters that could have been changed in string $c$. 45 46 Example 47 48 Input 49 50 ``` 51 7 52 53 a 54 55 b 56 57 cb 58 59 ab 60 61 cd 62 63 acbd 64 65 ab 66 67 ba 68 69 aabb 70 71 xxx 72 73 yyy 74 75 xyxyxy 76 77 a 78 79 bcd 80 81 decf 82 83 codes 84 85 horse 86 87 codeforces 88 89 egg 90 91 annie 92 93 egaegaeg 94 ``` 95 96 Output 97 98 ``` 99 1 100 0 101 2 102 0 103 3 104 2 105 3 106 ```