Find substring

2.4

7 votes
Hash function, Easy, String, Hashing algorithm
Problem

You are given two strings A and B. You have to find smallest substring of A such that it contains all the letters of string B. The letters in both the strings can be any ASCII character.

Input constraints
1T1000
1|A|1000 where A denotes the length of the string A.
1|B|1000 where B denotes the length of the string B.

Input format
First line contains an integer, T,denoting the number of test cases.
First line in each test case contains a string, A.
Second line in each test case contains a string B.

Output format
Print the smallest substring of A such that it contains all the letters of string B. If there is no such substring, print 1. If there are multiple such substring, print the one which starts first. Answer for each test case should be in a new line.

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

The smallest substring that contains all the letter of string TisT is ThisIsAT which contains 8 letters.

Editor Image

?