Hansels Ordeal II
All submissions for this problem are available.
Unable to understand Gretel's last clue, Hansel concludes that it must be nonsensical. He must now use the parchment to decode the remainder of the witch’s devious schemes. In this desperate attempt to foil her plans, Hansel requires your help yet again.
Given the string A containing the plans and string B containing Gretel's nonsense, determine the number of distinct substrings of A such that they do not contain string B as a substring.
The first line of input consists of a single integer T denoting the number of test cases. The following 2×T lines define the T test cases. Every test case consists of 2 lines. The first line of contains string A. The second contains string B.
Note: All the string characters are between lowercase 'a' and 'z'.
The output contains T lines, with every line consisting of a single integer - the number of possible substrings corresponding to each test case.
1 ≤ T ≤ 25
1 ≤ |A| ≤ 5×104
1 ≤ |B| ≤ 5×104
2 ababababa bab xyxyx yx
Distinct substrings for the 1st test case are a, b, ab, ba, aba.
Distinct substrings for the 2nd test case are x, y, xy.
|Time Limit:||1 - 3 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.