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 ```