BZOJ2780: [Spoj]8093 Sevenk Love Oimaster

Time Limit: 1 Sec  Memory Limit: 128 MB

Description

Oimaster and sevenk love each other.
But recently,sevenk heard that a girl named ChuYuXun was dating with oimaster.As a woman’s nature, s
evenk felt angry and began to check oimaster’s online talk with ChuYuXun.    Oimaster talked with Ch
uYuXun n times, and each online talk actually is a string.Sevenk asks q questions like this,    “how
 many strings in oimaster’s online talk contain this string as their substrings?”
有n个大串和m个询问,每次给出一个字符串s询问在多少个大串中出现过

Input

There are two integers in the first line,
the number of strings n and the number of questions q.
And n lines follow, each of them is a string describing oimaster’s online talk.
And q lines follow, each of them is a question.
n<=10000, q<=60000
the total length of n strings<=100000,
the total length of q question strings<=360000

Output

For each question, output the answer in one line.

Sample Input

3 3
abcabcabc
aaa
aafe
abc
a
ca

Sample Output

1
3
1

HINT

Source

鸣谢duan2提供译文

Solution

广义后缀自动机。

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注