题目描述
给定字符串 S,q 次询问,每次给出 l,r(1≤l≤r≤|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,1≤q≤2×105。
- Subtask 1(5 Points): |S|,q≤50
- Subtask 2(20 Points): q≤50
- Subtask 3(26 Points): S 中只含有
a
、b
- Subtask 4(23 Points): |S|≤2×104,q≤4×104
- Subtask 5(26 Points): 没有额外的限制。