 Server Time: Wed Nov 25, 2020 6:42 pm
 Welcome ( logout ) 1427 - Substring Frequency (II)  PDF (English) Statistics Forum
 Time Limit: 5 second(s) Memory Limit: 128 MB

A string is a finite sequence of symbols that are chosen from an alphabet. In this problem you are given a string T and n queries each with a string Pi, where the strings contain lower case English alphabets only. You have to find the number of times Pi occurs as a substring of T.

# Input

Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 500). The next line contains the string T (1 ≤ |T| ≤ 106). Each of the next n lines contains a string Pi (1 ≤ |Pi| ≤ 500).

# Output

For each case, print the case number in a single line first. Then for each string Pi, report the number of times it occurs as a substring of T in a single line.

2

5

ababacbabc

aba

ba

ac

a

abc

3

lightoj

oj

light

lit

Case 1:

2

3

1

4

1

Case 2:

1

1

0

# Notes

1.      Dataset is huge, use faster I/O methods.

2.       If S is a string then |S| denotes the length of S.

Problem Setter: Jane Alam Jan
 Developed and Maintained by JANE ALAM JAN Copyright © 2012 LightOJ, Jane Alam Jan