codeforces-scrape

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

1203D1.md (1954B)


      1 Source: https://codeforces.com/problemset/problem/1203/D1
      2 
      3 D1. Remove the Substring (easy version)
      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 The only difference between easy and hard versions is the length of the string.
     22 
     23 You are given a string $s$ and a string $t$, both consisting only of lowercase Latin letters. It is guaranteed that $t$ can be obtained from $s$ by removing some (possibly, zero) number of characters (not necessary contiguous) from $s$ without changing order of remaining characters (in other words, it is guaranteed that $t$ is a subsequence of $s$).
     24 
     25 For example, the strings "test", "tst", "tt", "et" and "" are subsequences of the string "test". But the strings "tset", "se", "contest" are not subsequences of the string "test".
     26 
     27 You want to remove some substring (contiguous subsequence) from $s$ of maximum possible length such that after removing this substring $t$ will remain a subsequence of $s$.
     28 
     29 If you want to remove the substring $s[l;r]$ then the string $s$ will be transformed to $s_1 s_2 \dots s_{l-1} s_{r+1} s_{r+2} \dots s_{|s|-1} s_{|s|}$ (where $|s|$ is the length of $s$).
     30 
     31 Your task is to find the maximum possible length of the substring you can remove so that $t$ is still a subsequence of $s$.
     32 
     33 Input
     34 
     35 The first line of the input contains one string $s$ consisting of at least $1$ and at most $200$ lowercase Latin letters.
     36 
     37 The second line of the input contains one string $t$ consisting of at least $1$ and at most $200$ lowercase Latin letters.
     38 
     39 It is guaranteed that $t$ is a subsequence of $s$.
     40 
     41 Output
     42 
     43 Print one integer — the maximum possible length of the substring you can remove so that $t$ is still a subsequence of $s$.
     44 
     45 Examples
     46 
     47 Input
     48 
     49 ```
     50 bbaba
     51 bb
     52 ```
     53 
     54 Output
     55 
     56 ```
     57 3
     58 ```
     59 
     60 Input
     61 
     62 ```
     63 baaba
     64 ab
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 2
     71 ```
     72 
     73 Input
     74 
     75 ```
     76 abcde
     77 abcde
     78 ```
     79 
     80 Output
     81 
     82 ```
     83 0
     84 ```
     85 
     86 Input
     87 
     88 ```
     89 asdfasdf
     90 fasd
     91 ```
     92 
     93 Output
     94 
     95 ```
     96 3
     97 ```