HIGHBABA - Highly Spiritual Baba

no tags 

A spiritual baba in Banani claims that, given two strings he can check if one string is available in another string as sub-sequence and not only that, he can even tell the minimum sub-array in which that sub-sequence exists. Now your friend wants to know if that spiritual baba is fraud or not. So, he wants you to make an application for him.

You are given two strings A & B. Now, find the minimum length sub-array of string ’A’ which contains the sub-sequence (string ‘B’). If such sub-sequence cannot be found, print -1.

Subsequence: suppose a string “abcdef” is given. Here, ”abcdef”, “abf”, “def”, “bce”, “a” are some example of sub-sequence of this string. But strings like “fea” and “dc” are not.

Input

The first line of the input contains an integer T (1 <= T <= 100) number of test cases. For each test case, two strings A (1 <= N <= 2500) and B (1 <= M <= 80) are given, each containing small letter English alphabet. Here N is length of string A and M is length of string B. Cases are separated by blank lines in input file.

Output

Output the case number and the expected answer for each test case.

Example

Input:
2
aabbaaccanbbbncc
abc

objectorientedprogramming
ii

Output:
Case 1: 6
Case 2: 15

hide comments
sinersnvrsleep: 2018-04-24 08:05:30

binary search with a little optimization does it plz if u are mentioning something mention it in full otherwise we think that our approach is wrong@Daksh

manya_cod4: 2018-01-04 17:48:31

Hi All. I solved it using DP. but i dont know how to solve by Binary Search. possible to give hints ? Thanks. :)

Gaurav Dahima: 2016-09-19 12:27:29

what is the expected complexity of the solution ???

Abhishek: 2016-09-18 06:49:59

Binary Search passes, but does it have a DP solution?

Shubham: 2016-06-20 16:57:44

stupid missed -1 which costed me many WA :( :( nothing needed simple brute force will pass with little optimizatn

rk: 2015-12-26 19:53:44

@problem setter getting rte plz check my solution

Last edit: 2015-12-26 20:28:15
Daksh: 2015-12-19 13:14:22

Binary Search... :)

Vipul Srivastava: 2015-12-03 13:52:13

Last edit: 2015-12-03 19:09:00

Added by:imranziad
Date:2015-11-25
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:AIUB CS Fest 2015 (Rawnak)