AT_tenka1_2014_final_e 田端でバタバタ

“重复字符串”是指存在一个非空字符串 $A$，使得该字符串可以表示为 $A+A$ 的形式。在语言学中，这也被称为“叠词”。日语中叠词非常多，通常的句子中也经常出现。这次我们来统计一下这样的字符串。 给定一个由小写字母组成的字符串 $S$，以及 $Q$ 个查询 $[a_i, b_i]$。对于每个查询，求 $S[a_i, b_i]$ 的所有非空子串中，属于重复字符串的那些子串的长度之和。如果存在多个相同的字符串，也要分别计数。 这里，$A+B$ 表示将字符串 $A$ 和 $B$ 连接起来。而 $S[x, y]$ 表示从字符串 $S$ 的第 $x$ 个字符到第 $y$ 个字符（包含两端）所截取的子串。

输入通过标准输入给出，格式如下： > $S$ > $Q$ > $a_1\ b_1$ > $a_2\ b_2$ > $\vdots$ > $a_Q\ b_Q$ - 第 $1$ 行给出字符串 $S$，$1 \leq |S| \leq 100000$，$|S|$ 表示字符串 $S$ 的长度。 - 第 $2$ 行给出整数 $Q$，表示查询的个数，$1 \leq Q \leq 100000$。 - 接下来 $Q$ 行，每行包含两个整数 $a_i, b_i$，表示第 $i$ 个查询，$1 \leq a_i \leq b_i \leq |S|$，以空格分隔。

对于每个查询，输出一个答案，每行一个，共 $Q$ 行。每个答案后都要换行。

## 部分分 如果你能正确解决 $1 \leq |S| \leq 1000$ 的测试用例，将获得部分分 $100$ 分。 如果你能正确解决 $1 \leq |S| \leq 20000$ 的测试用例，将再获得部分分 $100$ 分。 如果你能正确解决所有测试用例，将再获得 $150$ 分。 ## 样例解释 1 `koko` 和 `pyonpyon` 都是重复字符串。在第 $1$ 个查询中，考虑 `kokoropyonpyon`，其中有 `koko` 和 `pyonpyon` 两个重复字符串，所以答案是 $12$。第 $2$ 个查询中，考虑 `okoropyonpyon`，其中有 `pyonpyon`，所以答案是 $8$。第 $3$ 个查询中，考虑 `kokoropyonpyo`，其中有 `koko`，所以答案是 $4$。 ## 样例解释 2 `attatt`、`ttatta`、`tt`、`tt` 都是重复字符串。两个 `tt` 要分别计数。 ## 样例解释 3 请注意，可能会出现大量的重复字符串。 由 ChatGPT 4.1 翻译