← 返回题目列表

AtCoder · tenka1_2014_final_e

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_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

请注意,有时会出现大量重复字符串。