Chef and Substrings
All submissions for this problem are available.
Read problems statements in Mandarin Chinese here
Read problems statements in Russian here
Chef has a string S = S1S2 ... SN, consisting of N lowercase Latin letters. Also he has M pairs of integers Li, Ri (1 ≤ Li ≤ Ri ≤ N).For each pair Li, Ri, Chef writes out all distinct substrings of string S, which are started from positions Li, Li + 1, ..., Ri.
Your task is to help Chef. That is, for each pair, find out how many substrings that he needs to write.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains non-empty string S and the second line contains positive integer M.
Each of the next M lines contains a pair of integers Li, Ri.
For each pair of each test case print the required number of substrings.
- String S contains only lowercase Latin letters.
- 1 ≤ Li ≤ Ri ≤ N.
- Sum of all length's of S for test cases is not greater than 50000. Sum of all M values for test cases is not greater than 50000.
Input: 2 ababa 4 1 1 1 5 5 5 3 4 a 1 1 1 Output: 5 9 1 5 1
|Time Limit:||7 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.