String occurences 3 - MarisaOJ: Marisa Online Judge

Given a string

$S$ and

$q$ queries. Each queries is a string

$T$ , ask you how many times does

$T$ occur in

$S$ . ### Input - The first line contains string

$S$ . - The second line contains an integer

$q$ . - The next

$q$ line, each line contains a string, a query. ### Output - Print the answer for each query. ### Constraints -

$1 \le |S|,q \le 10^5$ . -

$1 \le \sum{|T|} \le 10^5$ . ### Example Input:

$abcab 3 ab d c$

Output:

$2 0 1$

Square root decomposition
	Frequency
	Tree query
	Inversions query
	Nearest vertex
	Dominating color
	String occurences 3
	Inversions query 2
	Pair
	Sparse update
	Tree
	Range query
	String concatenation
	Subarray distance
	Chameleon
	Knapsack
	Bit counting
	Subsequence queries
	Sub-subsequence
	Delete numbers
	Mode
	Marisa is happy
	Inversions query 3
	Upperbound
	23 path
	Yet another square root decomposition problem
	Marisa plays poker
	Wonderful world

Topic

Data structure

String

Hashing

Rating

1700

Solution (0)

Solution