马龙的字符串 ## 来源 ZOJ 10th Anniversary Contest (ZOJ3587) ## 题目描述 设S为字符串，令$S_{i...j}$代表S的从第i个字符到第j个字符的子串。 给定字符串S和T，计算满足以下条件的四元组(a, b, c, d)的个数：$S_{a...b}$ + $S_{c...d}$ = T，a≤b，c≤d，这里的加号（+）表示把两个字符串连接起来。 ## 输入描述 输入文件的第一行为整数Tc，表示测试数据个数。每个测试数据占两行，第一行为字符串S，第二行为字符串T。S和T的长度范围在[1, 100000]。S和T中均只包含字母字符。 ## 输出描述 对每个字符串，输出占一行，为求得的结果。 ## 样例输入 ```txt 1 aaabbb ab ``` ## 样例输出 ```txt 9 ```