NOI '18 P3 - Name

View as PDF
Submit solution
Points: 25 (partial)
Time limit: 4.0s
Memory limit: 1G
Problem types

You are given a string S, and q queries.

For each query, you are given a string T and two integers l, r. You are asked to output the number of distinct substrings of T that is not a substring of S[l..r]

String S[l..r] refers the substring of S from index l to r, i.e. slsl+1...sr−1sr.

Input Specification

The first line contains an string S.

The next line contains an integer q.

Each of the next q lines contains a string T and two integers l, r.

Output Specification

For each test case, output the answer.

Sample Input

Copy
scbamgepe
3
smape 2 7
sbape 3 8
sgepe 1 9

Sample Output

Copy
12
10
4
Data ranges
Case ∣S∣≤ Q≤　 ∑∣T∣≤ Properties
1 200 200 40000 T≤200
2 1000 200 40000 T≤200
3 1000 200 40000 T≤200
4 1000 200 5×105 None
5 1000 200 5×105 None
6 5×105 1 5×105 None
7 5×105 1 5×105 None
8 105 105 2×105 None
9 105 105 2×105 string is random
10 2×105 105 4×105 None
11 2×105 105 4×105 String is Random
12 3×105 105 6×105 None
13 3×105 105 6×105 string is random
14 4×105 105 8×105 None
15 4×105 105 8×105 string is random
16 5×105 105 106 None
17 5×105 105 106 String is random
18 2×105 105 106 None
19 3×105 105 106 none
20 4×105 105 106 none
21 5×105 105 106 none
22 5×105 105 106 none
23 5×105 105 106 none
24 5×105 105 106 none
25 5×105 105 106 none

For the first 17 test points all queries have l=1,r=|S|.

For all data, it is guaranteed that 1≤l≤r≤|S|,1≤|T|≤5×105

Comments

There are no comments at the moment.