lightoj1427

maksyuki 发表于 oj 分类,标签:
0

1427 - Substring Frequency (II)

InputA 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 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.

Sample Input

Output for Sample Input

25ababacbabcababa

ac

a

abc

3

lightoj

oj

light

lit

Case 1:2314

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.

 

题目类型:AC自动机

算法分析:将子串插入到Trie树中,然后使用cnt数组统计在文本串T中,相应子串出现的个数即可,注意子串可能出现重复的情况!!!由于n比较小,所以可以使用O(n^2)的枚举将标号后面重复的相应子串的个数求解得到