
ZOJ Problem Set  3587
Long long ago, there was a coder named Marlon. One day he picked two string on the street. A problem suddenly crash his brain... Let S_{i..j} denote the ith character to the jth character of string S. Given two strings S and T. Return the amount of tetrad (a,b,c,d) which satisfy S_{a..b} + S_{c..d} = T , a≤b and c≤d. The operator + means concate the two strings into one. InputThe first line of the data is an integer Tc. Following Tc test cases, each contains two line. The first line is S. The second line is T. The length of S and T are both in range [1,100000]. There are only letters in string S and T. OutputFor each test cases, output a line for the result. Sample Input1 aaabbb ab Sample Output9 Author: CHEN, Weijie Contest: ZOJ 10th Anniversary Contest 