# 8758. Cover the string

## Problem code: MAIN8_E

Given two strins A and B. You have to find the length of the smallest substring of A, such that B is the subsequence of this substing.
Formally speaking
you have to find the lenght of smallest possible string S such that
S is the substring of A
B is the subsequence S
Note: Subsequence of an string S is obtained by deletnig some (possibly none) of the characters from it. for example "ah" is the subsequecne of "aohol"

Given two strins A and B. You have to find the length of the smallest substring of A, such that B is the subsequence of this substing.

Formally speaking

you have to find the lenght of smallest possible string S such that

S is the substring of A

B is the subsequence S

Note: Subsequence of an string S is obtained by deletnig some (possibly none) of the characters from it. for example "ah" is the subsequecne of "aohol"

### Input

First line contains T, the number of test cases. Then T test cases follow, 2 lines for each test case, 1st contains A and 2nd contain B.

|A|<=20000, |B|<=100

### Output

For each test case print the answer in a new line. if no such substring exists print -1 instead.

### Example

```Input:
2
acs
ghkkhllhjkhthkjjht
hh

Output:
10
3```

 Added by: Mahesh Chandra Sharma Date: 2011-04-20 Time limit: 4s Source limit: 50000B Memory limit: 256MB Cluster: Pyramid (Intel Pentium III 733 MHz) Languages: All Resource: Own problem used for NSIT-IIITA Main contest #8

2011-05-05 14:05:29 V0iD!
anyone using regex in java to solve this?? any luck at all?? am always getting tle.. :(
2011-05-04 04:28:56 Kashyap Krishnakumar
@problem setter: I think the solutions have not been rejudged after change of test cases. So a lot of solutions have passed in lower time.
2011-04-29 18:22:57 Buda IM
@Santiago Palacio
It says that you should print -1 if that is the case. Therefore that case is possible.
2011-04-28 21:39:57 Santiago Palacio
There is no case where B cannot be made from A right?
2011-04-26 11:34:13 Mahesh Chandra Sharma
@ justine. If you are getting TLE then optimize your code. Thats all what I can say ;)
2011-04-26 11:33:01 Mahesh Chandra Sharma
I have added a rigorous test case, on which some of the Accepted solutions failed. Please resubmit your solution in case yours failed too.
2011-04-26 11:30:58 Mahesh Chandra Sharma
@Azamat T<=20

Last edit: 2011-04-26 11:32:28
2011-04-25 16:10:45 justine
2011-04-24 19:10:05 justine
please tell me why i m getting TLE.
my code has complexity O[lenA*lenB].
am i getting infinite loop??
my ans id is:5007812.

Last edit: 2011-04-24 19:10:31
2011-04-24 12:53:48 sandeep pandey
is it possible to accept d O[N^2] solution??

NO

Last edit: 2013-01-31 18:01:55