All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
You are given a string S and N queries. Each query is defined by two integers - Li and Pi. Count the number of strings of the length Li that occur exactly Pi times (as the consecutive substrings) in the string S.
The first line of input contains the string S.
The second line of input contains the integer N - the number of queries.
Then there are N lines, the i-th one contains numbers Li and Pi for the i-th query.
For each query output the answer at the corresponding line of the output.
- 1 ≤ |S| ≤ 50, 1 ≤ N ≤ 100 : 13 points.
- 1 ≤ |S| ≤ 1000, 1 ≤ N ≤ 10000 : 27 points.
- 1 ≤ |S| ≤ 200000, 1 ≤ N ≤ 500000 : 60 points.
- 1 ≤ Li, Pi ≤ N
Input: abacaba 1 3 2 Output: 1
The only such string is aba.
|Tags||ltime13, medium, suffix_automata, trie, xcwgf666|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.