Entangled Strings

All submissions for this problem are available.
Chef is now off his restaurant hardwork, but that doesn't mean he is allowed to rest... After all, he will be hosting a dinner to his cousins who came visit him all the way from Gigaland (as we know, Chef lives in Byteland).
Once they arrived, Chef got a bit worried as he saw that they were bringing along their loud children with them... Besides all the noise, he would even have to cook extra food, so he decided to keep children busy and gave them two strings S1 and S2. He also has an integer L, which he gave to the children as well.
For a string S=c_{1} c_{2} ... c_{N}, let S[a,b] denote c_{a} c_{a+1} ... c_{b1} c_{b}, that is, the substring starting at a^{th} character and ending at b^{th} character. For each 1 ≤ i ≤ L, chef wants the children to know how many tuples (a, b, c, d) exist for which S1[a, b] = S2[c, d] and length of S1[a,b] is i.
Hopefully Chef will be able to cook in peace now :)
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a the string S1. The second contains the string S2. The third line contains the integer L.
Output
For each test case, output a single line containing L space separated integers, where the i^{th} integer is number of common substrings of length i.
Constraints
 1 ≤ T ≤ 15
 All strings are composed of characters az.
 length of any string ≤ 2*10^{5}
 In any test file, the sum of lengths of all strings is at most 2*10^{6}
Subtask 1(15 points)
L = 1
Subtask 2(20 points)
L ≤ 10
Subtask 3(15 points)
length of any string is at most 200
Subtask 4(20 points)
length of any string is at most 5000
Subtask 5 (30 points):
No special constraints
Example
Input: 4 abcd abcd 3 abab babc 4 abcbca acccca 5 abxyz xyzab 4Output: 4 3 2 6 3 1 0 12 1 0 0 0 5 3 1 0
Explanation
Example case 2. Common substrings of length 1 are (a,b,c,d) = (0,0,1,1), (2,2,1,1), (1,1,0,0), (1,1,2,2), (3,3,0,0), (3,3,2,2).
Common substrings of length 2 are (0, 1, 1, 2), (1, 2, 0, 1), (2, 3, 1, 2).
Common substrings of length 3 are (1, 3, 0, 2).
There is no common substring of length 4.
Author:  utkarsh_lath 
Tester:  
Editorial  http://discuss.codechef.com/problems/TANGLED 
Tags  hard, lcp, ltime02, suffixarray, utkarsh_lath 
Date Added:  25072013 
Time Limit:  8 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, 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, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 