5488: Singing Superstar
内存限制：128 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
Ke Ke is a cheerful, enthusiastic girl. She
dreams of singing happily every day. One day, while practicing singing,
Ke Ke accidentally discovered that there are some words that can make
the song better. She called these words "SuperstarWords".
After a lot of attempts, she found that in each song, there are a total of n "SuperstarWords". She wants to know the maximum number of disjoint occurrences of each "SuperstarWords" in her song.
Note : one occurrence means that the SuperstarWord is a continuous substring of the song at a certain position.
For example: The maximum number of disjoint occurrences of "aba" in "abababa" is 2
After a lot of attempts, she found that in each song, there are a total of n "SuperstarWords". She wants to know the maximum number of disjoint occurrences of each "SuperstarWords" in her song.
Note : one occurrence means that the SuperstarWord is a continuous substring of the song at a certain position.
For example: The maximum number of disjoint occurrences of "aba" in "abababa" is 2
输入
The first line contains an integer T(T≤5), denoting the number of test cases.
The first line of each test case contains one string s(1≤|s|≤105), denoting a song.
The second line of each test case contains one integer n(1≤n≤105), denoting the number of SuperstarWords
The next n lines contains contains one string ai(1≤ |ai| ≤30), denoting one SuperstarWords
It is guaranteed that for all test cases, ∑|s|≤4∗105, ∑|ai|≤4∗105
Note:All input string character sets are lowercase English letters
The first line of each test case contains one string s(1≤|s|≤105), denoting a song.
The second line of each test case contains one integer n(1≤n≤105), denoting the number of SuperstarWords
The next n lines contains contains one string ai(1≤ |ai| ≤30), denoting one SuperstarWords
It is guaranteed that for all test cases, ∑|s|≤4∗105, ∑|ai|≤4∗105
Note:All input string character sets are lowercase English letters
输出
For each test case, output n lines, each line has one integer, indicating the answer.
样例输入 复制
2
abababbbaanbanananabanana
3
aba
ababa
nana
nihaoxiexiexiaolongbaozaijian
3
qwer
taihaotinleba
xiexi
样例输出 复制
2
1
2
0
0
1