All submissions for this problem are available.
Your friend had secretly installed a key logger in your system; after all he needed to crack your friend’s book password. Fortunately you came to know about this. You know your password p, and you intentionally write long sentence s to confuse your friend. You now want to calculate the chances your friend will be able to crack your password. You know that your friend can do three operations on full or part of the sentence s, insert a character anywhere, delete any character or replace some character with some other. All these operation cost one thinking ability. So now you wish to calculate the least thinking ability your friend should have to guess the password from the sentence.
The first line of input consists of the number of test cases T. Then T lines follow each describing a test case. The first line of each test case consist of the sentence s and the next line contains the password p. Both of these strings are composed of lower case alphabets only.
For each test case print a line with the minimum thinking ability required to guess the password.
1≤ |s|,|p| ≤ 103
Input: 2 retreiveretreeveretreev retrieve itiseasytoguessifitisqwerty qwerty Output: 1 0
Example case 1. The string “retrieve” would cost 2 because the best one can do is replace 2 characters. The string retreeve just needs 1 replacement and is the closest.
Example case 2. The password is already a part of the string and so no thinking ability required.
|Time Limit:||0.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP 4.3.2, CPP14, GO, JAVA|
Fetching successful submissions
If you are still having problems, see a sample solution here.