QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB Total points: 100
[+5]

# 532. 区间本质不同子串

Statistics

题目描述

给定字符串 Sq 次询问,每次给出 l,r(1lr|S|),你需要求出 S[l:r] 本质不同的子串数量。

输入格式

输入的第一行包含一个字符串 S

接下来一行包含一个整数 q

接下来 q 行,每行两个整数 l,r,描述一组询问。

输出格式

输出 q 行,每行一个整数,表示答案。

样例数据

样例 1 输入

helloeveryonenationalolympiadininformaticswilltakeplaceinaugustgoodlucktoeveryonebythewaythisisejudgecontestadministrationsystem
5
1 58
18 46
35 57
25 40
55 56

样例 1 输出

1662
420
267
129
3

样例 2 输入

browseprivatelyexplorefreelydefendyourselfagainsttrackingandsurveillancecircumventcensorship
5
1 30
15 45
20 60
30 70
40 80

样例 2 输出

447
476
830
832
832

样例 3

见下发文件

子任务

对于所有数据,1|S|2×105,1q2×105

  • Subtask 1(5 Points): |S|,q50
  • Subtask 2(20 Points): q50
  • Subtask 3(26 Points): S 中只含有 ab
  • Subtask 4(23 Points): |S|2×104,q4×104
  • Subtask 5(26 Points): 没有额外的限制。