JZPGYZ - Sevenk Love Oimaster

no tags 

 

    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.
Example
Input:
3 3
hi,I'mChuYuXun..YouaresohandsomethatIfallinlovewithyou
butIlovesevenk..you'dbettergoaway
55555555555
ChuYuXun
you
55555555
Output:
1
2
1

hide comments
Raihat Zaman Neloy: 2016-06-13 12:06:58

10^5 * 600 also passes the TL :) Nice problem to solve :)

Ankita Victor: 2015-06-21 06:54:19

how is the answer to the last test case 1?

Jacob Plachta: 2014-02-13 14:43:10

Some of the constraints regarding sums of string lengths aren't met.

Sotirios Nikoloutsopoulos: 2012-06-18 14:09:37

@Tom Chen , can you tell me why my submission with ID : 7171738 gets WA?

Edit : Now i get TLE , can KMP pass?

Last edit: 2012-06-19 16:12:38
Radhakrishnan Venkataramani: 2011-06-01 00:26:07

Can u tell whats the size of input File ?

张钧瑞: 2011-04-17 03:23:00

The task is so difficult for me to solve~

mike_nzk: 2010-12-20 02:12:47

The question is "how many strings",so you should output the number of strings, not the number of substrings.

Garg Ankit: 2010-12-19 22:15:04

the last test case in the example above should yield the answer 4(according to me). Can anyone explain how is it 1?

Robert Gerbicz: 2010-12-19 22:03:18

After about ~20 sigabrt I've discovered that assert(0<=n&&0<=q); gets also runtime error, what is a big mistake.

It would be good to correct/update the tests.

Last edit: 2010-12-19 22:05:23
mike_nzk: 2010-12-19 06:29:08

I used an O(total_length_of_question_strings*log(total_length_of_n_strings)) algorithm and got AC. The time limit is not strict at all :)

Last edit: 2010-12-19 06:30:30

Added by:Tom Chen
Date:2010-12-18
Time limit:0.100s-0.161s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem