首页 > 题解 > bzoj 2780 [Spoj]8093 Sevenk Love Oimaster

bzoj 2780 [Spoj]8093 Sevenk Love Oimaster

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, sevenk felt angry and began to check oimaster's online talk with ChuYuXun. Oimaster talked with ChuYuXun 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?"

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

题解

题意就是给n个串和m个串,求这m个串是n个串中多少个串的子串。

n个串建个广义后缀自动机,注意建的时候对于每个点标记一下这个点有多少个串用了这个点,多个串的化就外挂一个链表。

然后对每个询问串在自动机上匹配,匹配到的点其Parent树子树中的节点就可以包含这个串。我们把Parent树的dfs序找出来,那么这个题就转换成了hh的项链那个题,搞个树状数组就解决了。

这题一遍过样例一遍a,很爽


1 COMMENT

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×