HIGHBABA  Highly Spiritual Baba
A spiritual baba in Banani claims that, given two strings he can check if one string is available in another string as subsequence and not only that, he can even tell the minimum subarray in which that subsequence 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 subarray of string ’A’ which contains the subsequence (string ‘B’). If such subsequence cannot be found, print 1.
Subsequence: suppose a string “abcdef” is given. Here, ”abcdef”, “abf”, “def”, “bce”, “a” are some example of subsequence 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:
20180424 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:
20180104 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:
20160919 12:27:29
what is the expected complexity of the solution ??? 

Abhishek:
20160918 06:49:59
Binary Search passes, but does it have a DP solution? 

Shubham:
20160620 16:57:44
stupid missed 1 which costed me many WA :( :( nothing needed simple brute force will pass with little optimizatn 

rk:
20151226 19:53:44
@problem setter getting rte plz check my solution


Daksh:
20151219 13:14:22
Binary Search... :)


Vipul Srivastava:
20151203 13:52:13
Last edit: 20151203 19:09:00 
Added by:  imranziad 
Date:  20151125 
Time limit:  0.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 
Resource:  AIUB CS Fest 2015 (Rawnak) 