codeforces-scrape

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

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\}$.