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 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.
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 the case number and the expected answer for each test case.
Input: 2 aabbaaccanbbbncc abc objectorientedprogramming ii Output: Case 1: 6 Case 2: 15
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
Hi All. I solved it using DP. but i dont know how to solve by Binary Search. possible to give hints ? Thanks. :)
what is the expected complexity of the solution ???
Binary Search passes, but does it have a DP solution?
stupid missed -1 which costed me many WA :( :( nothing needed simple brute force will pass with little optimizatn
@problem setter getting rte plz check my solution
Binary Search... :)
Last edit: 2015-12-03 19:09:00