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
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
Siarhei Kulik: 2010-12-18 20:41:52

Can O(total_length_of_question_strings*log(total_length_of_n_strings)) pass or should I search for a better algo?

Last edit: 2010-12-18 20:42:13
[Trichromatic] XilinX: 2010-12-18 18:18:05

I think brute-force can not pass it with 2 second time limit, if the test data is well-designed. This problem is "E - Dominating Patterns" from ACM ICPC Asia Regional Contest, Hefei 2009/2010. (Even though in the real-time contest KMP algorithm can easily pass.)

Last edit: 2010-12-18 19:38:06
[Trichromatic] XilinX: 2010-12-18 16:21:26

Why not 2 seconds?
[reply]:because I don't want brute-force algorithm to pass it :) so make it as strict as possible

Last edit: 2010-12-18 16:46:42
Tom Chen: 2010-12-18 15:11:15

I change the time limit to 1.5s...maybe old one is too strict..

Tom Chen: 2010-12-18 12:02:26

now testcases are added...sorry for inconvenience...

Last edit: 2010-12-18 11:57:00

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