1492C.md (1932B)
1 Source: https://codeforces.com/problemset/problem/1492/C 2 3 C. Maximum width 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Your classmate, whom you do not like because he is boring, but whom you respect for his intellect, has two strings: $s$ of length $n$ and $t$ of length $m$. 22 23 A sequence $p_1, p_2, \ldots, p_m$, where $1 \leq p_1 \lt p_2 \lt \ldots \lt p_m \leq n$, is called beautiful, if $s_{p_i} = t_i$ for all $i$ from $1$ to $m$. The width of a sequence is defined as $\max\limits_{1 \le i \lt m} \left(p_{i + 1} - p_i\right)$. 24 25 Please help your classmate to identify the beautiful sequence with the maximum width. Your classmate promised you that for the given strings $s$ and $t$ there is at least one beautiful sequence. 26 27 Input 28 29 The first input line contains two integers $n$ and $m$ ($2 \leq m \leq n \leq 2 \cdot 10^5$) — the lengths of the strings $s$ and $t$. 30 31 The following line contains a single string $s$ of length $n$, consisting of lowercase letters of the Latin alphabet. 32 33 The last line contains a single string $t$ of length $m$, consisting of lowercase letters of the Latin alphabet. 34 35 It is guaranteed that there is at least one beautiful sequence for the given strings. 36 37 Output 38 39 Output one integer — the maximum width of a beautiful sequence. 40 41 Examples 42 43 Input 44 45 ``` 46 5 3 47 abbbc 48 abc 49 ``` 50 51 Output 52 53 ``` 54 3 55 ``` 56 57 Input 58 59 ``` 60 5 2 61 aaaaa 62 aa 63 ``` 64 65 Output 66 67 ``` 68 4 69 ``` 70 71 Input 72 73 ``` 74 5 5 75 abcdf 76 abcdf 77 ``` 78 79 Output 80 81 ``` 82 1 83 ``` 84 85 Input 86 87 ``` 88 2 2 89 ab 90 ab 91 ``` 92 93 Output 94 95 ``` 96 1 97 ``` 98 99 Note 100 101 In the first example there are two beautiful sequences of width $3$: they are $\{1, 2, 5\}$ and $\{1, 4, 5\}$. 102 103 In the second example the beautiful sequence with the maximum width is $\{1, 5\}$. 104 105 In the third example there is exactly one beautiful sequence — it is $\{1, 2, 3, 4, 5\}$. 106 107 In the fourth example there is exactly one beautiful sequence — it is $\{1, 2\}$.