#3311. 「ZJOI2020」字符串

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

Bob 喜欢字符串。

Bob 觉得,重复两遍的字符串是优美的,例如,aaseseabcabcbaabaaabababab 是优美的串,而 abaadeadseseseabba 不是。更具体地说,如果一个字符串 S 能够被写成两个相同的字符串前后拼接的形式,即存在字符串 P 使得 S = PP ,那么 S 就是优美的。

Bob 有一个长度为 n 的字符串 T = T_1 T_2 \cdots T_n 。现在他想知道,给定 T 的一个子串 Q = T[l \dots r] ,这个子串 Q 内一共包含多少种本质不同的优美的串作为子串。如果两个串相同,但是出现的位置不同,那么这两个串不是本质不同。

Bob 一共有 q 组不同的询问,你需要快速计算出答案。

输入格式

第一行输入两个整数 n, q 。第二行输入一个只包含小写字母 a b 的字符串 T

接下来 q 行,每行输入两个整数 l, r ,表示一组询问。

输出格式

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

样例

样例输入 1

11 5
aabaabaaaab
1 11
1 6
7 10
5 5
3 8

样例输出 1

5
2
2
0
2

样例解释 1

|T| aaaaaaabaabaaabaabbaabaa 这些本质不同的优美的串。

样例 2

见附加文件中 string2.instring2.out

数据范围与提示

对于前 10\% 的数据, n\le 100

对于前 20\% 的数据, n\le 500

对于前 40\% 的数据, n\le 5000

对于另外 20\% 的数据,保证 T 中所有的优美的串的个数不超过 10^6 ,这里位置不同的串被视为不同的。

对于另外 20\% 的数据, q = 1

对于 100\% 的数据, 1\le n, q\le 2\times 10^5, 1\le l\le r\le n T 只包含小写字母 ab