MAIN8_E - Cover the string

no tags 

 

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
aaddddcckhssdd
acs
ghkkhllhjkhthkjjht
hh

Output:
10
3

hide comments
karthik_kamal: 2013-07-19 10:40:22

my submission gave me wa ans.........

Last edit: 2013-07-19 10:41:02
V0iD!: 2011-05-05 12:05:29

anyone using regex in java to solve this?? any luck at all?? am always getting tle.. :(

Kashyap Krishnakumar: 2011-05-04 02:28:56

@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.

Buda IM (retired): 2011-04-29 16:22:57

@Santiago Palacio
It says that you should print -1 if that is the case. Therefore that case is possible.

Santiago Palacio: 2011-04-28 19:39:57

There is no case where B cannot be made from A right?

Mahesh Chandra Sharma: 2011-04-26 09:34:13

@ justine. If you are getting TLE then optimize your code. Thats all what I can say ;)

Mahesh Chandra Sharma: 2011-04-26 09:33:01

I have added a rigorous test case, on which some of the Accepted solutions failed. Please resubmit your solution in case yours failed too.

Mahesh Chandra Sharma: 2011-04-26 09:30:58

@Azamat T<=20

Last edit: 2011-04-26 09:32:28
justine: 2011-04-25 14:10:45

@problem setter:please reply me.-(

justine: 2011-04-24 17:10:05

please tell me why i m getting TLE.
my code has complexity O[lenA*lenB].
am i getting infinite loop??
please response.
my ans id is:5007812.

Last edit: 2011-04-24 17:10:31

Added by:Mahesh Chandra Sharma
Date:2011-04-20
Time limit:0.374s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem used for NSIT-IIITA Main contest #8