#PQJ472x425. QOJ 472_425

    ID: 2987 传统题 3000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:ZJOI 2020字符串前缀和

QOJ 472_425

1 字符串 1.1 题目描述 Bob 喜欢字符串。 Bob 觉得,重复两遍的字符串是优美的,例如,aa,sese,abcabc,baabaa,abababab 是优 美的串,而ab,aadead,sesese,abba 不是。更具体地说,如果一个字符串S 能够被写成两个 相同的字符串前后拼接的形式,即存在字符串P 使得S = PP,那么S 就是优美的。 Bob 有一个长度为n 的字符串T = T1T2 · · · Tn。现在他想知道,给定T 的一个子串 Q = T[l · · · r],这个子串Q 内一共包含多少种本质不同的优美的串作为子串。如果两个串相同, 但是出现的位置不同,那么这两个串不是本质不同。 Bob 一共有q 组不同的询问,你需要快速计算出答案。 1.2 输入格式 第一行输入两个整数n, q。第二行输入一个只包含小写字母a 和b 的字符串T。 接下来q 行,每行输入两个整数l, r,表示一组询问。 1.3 输出格式 输出q 行,每行一个整数表示答案。 1.4 样例输入1 11 5 aabaabaaaab 1 11 1 6 7 10 5 5 3 8 1.5 样例输出1 5 2 2 0 2 2

1.6 样例解释1 |T| 有aa,aaaa,abaaba,aabaab,baabaa 这些本质不同的优美的串。 1.7 样例输入输出2 见下发文件 1.8 数据范围与约定 对于前10% 的数据,n ≤100。 对于前20% 的数据,n ≤500。 对于前40% 的数据,n ≤5000。 对于另外20% 的数据,保证T 中所有的优美的串的个数不超过106,这里位置不同的串被 视为不同的。 对于另外20% 的数据,q = 1。 对于100% 的数据,1 ≤n, q ≤200000,1 ≤l ≤r ≤n,T 只包含小写字母a 和b。 3