String occurences 3 - MarisaOJ: Marisa Online Judge

String occurences 3

Time limit: 4000 ms
Memory limit: 768 MB
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 ```