STRMATCH - Match me if you can


After watching the movie "Catch me if you can" professor Mahammad became very confident about creating a new problem for his programmers. As some procedures in his research heavily depend on string matching, now, he wants to check his beginner programmers' skills in this topic as well. His task is very simple. Professor gives you a random string and several queries. For each of the query string, you have to count the number of its occurrences in the string provided by professor.

Input

First line of the input section contains two positive integers N and Q, which define the length of professor's string and the number of queries, respectively.

Second line contains professor's string having length N (N ≤ 3000).

The following Q lines contain a query string having nonzero length.

Output

For each of the queries, output the number of the desired count of the occurences.

Note: The sum of the length of query strings does not exceed 500000. And please, do consider the time limit, because the problem can be solved in both slow and fast languages.

Example

Input:

7 5
acababa
a
bb
caba
aba
karp

Output:

4
0
1
2
0


hide comments
julkas: 2017-10-08 14:48:50

@mahilewets. Don't think about KMP and other advanced algos. Try simple and short solution. My Python solution ~ 10 lines of code.

mahilewets: 2017-10-07 06:58:15

Maybe try something like more general KMP

amancaj: 2017-10-06 15:01:56

any hints on how to solve this?
the obvious straightforward string.find gives TLE... (tried in Python3.5 & C++)

wisfaq: 2017-10-02 16:26:15

The reason why I enter duplicate solutions is the instability of the SPOJ timing system.
You can see that my timings vary greatly for exact the same code.

Anyhow, you disqualified one or more of my solutions.
Disqualifying solutions by problem setters should be used only for getting rid of solutions by cheaters and the like. Now, thanks to you I have again acquired disqualified solutions while I did nothing wrong, except entering a solution more than once.
re: We were sorry about the inconvenience. However, we corrected our mistakes and we are now definitely sure that no further issues root from us.

Last edit: 2017-10-02 16:39:18
mahmud2690: 2017-10-02 15:36:02

@wisfaq: so sorry for inconvenience, we were having a debate on time limit and allowed languages. That is why we had to discard a few duplicate solutions, now everything is okay.

=(Francky)=> Please consider spoj_psolver not as beta_testers. Please publish a problem when fully ready, tested. Please do not delete comments of serious psolvers. Regards.
re: Okay, we will do our utmost in order to prevent such cases.

Last edit: 2017-10-02 15:43:27
Pranay: 2017-10-01 16:03:55

kmp times out ?

re: Yes, of course. The intended solution is something faster than KMP.

Last edit: 2017-10-01 16:11:03
julkas: 2017-10-01 13:43:19

@mahmud2690 Nice problem.
P.S. Time limit is weak. My FIFO C++ solution is ~ 0.4s.
re: yeah, we did not consider alluring features of C++ which you used in your solution.
P.S. It's all right. My greetings to sunny Baku. My dream city.
re: Thanks for nice words. My e-mail is tr0j4n034@gmail.com. We can discuss further by e-mail if you wish. :)

P.S. Thank you. I have some questions. I'll try to mail it.

Last edit: 2017-10-01 16:04:20
[Rampage] Blue.Mary: 2017-09-29 11:08:55

Do the input strings contain lowercase English letters only?

(btw, the problem can be solved within the time limit even if N <= 500000.)

re: yes, input contains only lowercase english letters.
and thank you for extra feedback about N <= 500000 case.

Last edit: 2017-09-29 11:14:36

Added by:mahmud2690
Date:2017-09-29
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Me, MYSELF & I