codeforces-scrape

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

1295C.md (1715B)


      1 Source: https://codeforces.com/problemset/problem/1295/C
      2 
      3 C. Obtain The String
      4 
      5 time limit per test
      6 
      7 1 second
      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 two strings $s$ and $t$ consisting of lowercase Latin letters. Also you have a string $z$ which is initially empty. You want string $z$ to be equal to string $t$. You can perform the following operation to achieve this: append any subsequence of $s$ at the end of string $z$. A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements. For example, if $z = ac$, $s = abcde$, you may turn $z$ into following strings in one operation:
     22 
     23 1. $z = acace$ (if we choose subsequence $ace$);
     24 2. $z = acbcd$ (if we choose subsequence $bcd$);
     25 3. $z = acbce$ (if we choose subsequence $bce$).
     26 
     27 Note that after this operation string $s$ doesn't change.
     28 
     29 Calculate the minimum number of such operations to turn string $z$ into string $t$.
     30 
     31 Input
     32 
     33 The first line contains the integer $T$ ($1 \le T \le 100$) — the number of test cases.
     34 
     35 The first line of each testcase contains one string $s$ ($1 \le |s| \le 10^5$) consisting of lowercase Latin letters.
     36 
     37 The second line of each testcase contains one string $t$ ($1 \le |t| \le 10^5$) consisting of lowercase Latin letters.
     38 
     39 It is guaranteed that the total length of all strings $s$ and $t$ in the input does not exceed $2 \cdot 10^5$.
     40 
     41 Output
     42 
     43 For each testcase, print one integer — the minimum number of operations to turn string $z$ into string $t$. If it's impossible print $-1$.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 3
     51 aabce
     52 ace
     53 abacaba
     54 aax
     55 ty
     56 yyt
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 1
     63 -1
     64 3
     65 ```