All submissions for this problem are available.
Chef's best friend Jerry gives Chef a string A and wants to know the number of string A that can be obtained from another string B. A is made up of unique characters and every character in B can also be found in A. Chef is only allowed to remove string A from string B when it appears as a substring in string B. After one removal, the gap created will be closed and Chef can repeat the process.
Chef wants you to help Jerry to find the answer.
The first line of the input contains T, the number of test cases.
The first line of each test case contains the string A.
The second line of each test case contains the string B.Note: Please trim trailing whitespaces
For each test case, output a single line consisting of the number of string A that can be obtained from string B as described.
- 1 ≤ T ≤ 20
- 1 ≤ |A| ≤ 26
- A is made up of uppercase alphabet only
- A does not have repeated characters
- 1 ≤ |B| ≤ 3×105
- B only contains characters present in A
Input: 2 TIGER GTIGETIGERRERTIGTTIGERIGERER HELO HELHELLOO Output: 5 0
Test case 1: 5 TIGERs can be obtained from code B as follows:
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.