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 occurrences.

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

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

hide comments
2024-06-13 16:10:34 poopoo
DON'T LOOK, if you don't wanna spoil the problem If you're getting TLE with solution with complexity of O(N^2 + |Q|), if you're using C++'s map consider using unordered map and also initialize the unordered map with (n * n * 5) as initial bucket size. This is because unordered maps use hash so it's faster than usual map. Secondly each time number of elements inside an unordered map overflows some constant multiplied by its bucket size, it doubles its size, so the complexity of setting a value inside an unordered map with initial bucket size of zero becomes O(lgn). But if you initialize it with large initial bucket size, it never overflows so the complexity becomes O(1).

Last edit: 2024-06-13 22:41:14
2020-10-12 11:30:40
getting TLE with KMP ?? what should i Do??
2020-09-09 13:23:58
If you get TLE, use fast IO. And if using c ++ use '\ n' instead of endl.
2020-08-04 16:37:18
Used Suffix automaton, probably the best string data structure
2020-07-24 18:33:33
Nice problem. Solved using Rabin-Karp algorithm
2020-07-09 05:20:57
AC with SAM O(n + 5e5)
O(n + 5e5*log(26) ) will TLE :)) how ???
2020-02-15 14:36:39
easy......
2019-10-28 14:33:41 narek
Getting TLE for O(n^2 + |Q|) using tries. It seems it works like that in the comments

Or are we supposed to implement a suffix array / suffix tree


Last edit: 2019-10-28 14:38:38
2019-08-12 11:55:05
1. Don't post any source code here.
2. Please be careful, leave short comments only. Don't spam here.
3. For more discussion (hints, ideas, solutions) please visit our forum.
4. Authors of the problems are allowed to delete the post and use html code here (e.g. to provide some useful links).
2019-01-01 19:11:09
Really nice test cases. Hashing just wouldnt work. In the end used trie with O(n^2 + |S|) complexity.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.