#P17700. 区间本质不同子串个数
区间本质不同子串个数
题目描述
给定一个长度为 的仅包含小写字母的字符串 , 次询问由 的第 到第 个字符组成的字符串包含多少个本质不同的非空子串。
定义两个字符串 相同当且仅当 并且对于 都有 。
输入格式
第一行一个长度为 的字符串 。
第二行一个整数 ,表示询问次数。
接下来 行,第 行包含两个整数 ,描述第 次询问。
输出格式
行,每行一个整数,表示第 次询问的答案。
输入输出样例 #1
输入 #1
aababc
3
1 2
2 4
3 6
输出 #1
2
5
9
说明/提示
样例 1 解释
- 第一次询问,字符串为 ,包含 , 共 种本质不同子串。
- 第二次询问,字符串为 ,包含 $\texttt{a},\texttt{b},\texttt{ab},\texttt{ba},\texttt{aba}$, 共 种本质不同子串。
- 第三次询问,字符串为 ,包含 ,,,,,,,, 共 种本质不同子串。
数据规模与约定
- 对于 的数据,满足 ,。
- 对于 的数据,满足 ,,。