問題文
重复字符串是指可以表示为某个非空字符串 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_Q b_Q
- 1 字符串 给出了 S\ (1 ≦ |S| ≦ 100000) 。 (|S| 是一个字符串 让它代表 S 长度)
- 2 行包含一个表示查询数量的整数。 Q\ (1 ≦ Q ≦ 100000) 。 表示
- 3 从行 Q 行给出了查询信息。其中 一个整数,表示第 i\ (1 ≦ i ≦ Q) 行中, i 个查询的信息 a_i, b_i\ (1 ≦ a_i ≦ b_i ≦ |S|) 用空格分隔。
出力
每个查询的答案是 如果 1 逐行 Q 行。在输出末尾添加换行符。
部分点
1 ≦ |S| ≦ 1000 的所有测试用例都正确回答 ,作为部分点 如果 100 点。 如果您正确回答了所有满足
1 ≦ |S| ≦ 20000 的所有测试用例都回答正确 ,进一步作为部分点 100 点。 如果您正确回答了所有满足
如果所有测试用例都回答正确, 150 点。 如果您正确回答了所有满足
入力例1
kokoropyonpyon 3 1 14 2 14 1 13
出力例1
12 8 4
koko和
按字典顺序比较pyonpyon对应于重复字符串。
有
1 在第二个查询中,kokoropyonpyon。
来自koko、pyonpyon可以得到第 2重复字符串,所以答案是 12 。
2 在第二个查询中,okoropyonpyon。
来自pyonpyon存在,所以答案是 8 。
3 在第二个查询中,kokoropyonpyo。
来自koko存在,所以答案是 4 。
入力例2
rattatta 5 2 7 3 8 3 4 3 3 1 8
出力例2
10 10 2 0 16
attatt, ttatta, tt, tt对应于重复字符串。tt 2 个体是不同的。
入力例3
aaaaaaaaaa 1 1 10
出力例3
110
请注意,有时会出现大量重复字符串。