CF245H · Queries for Number of Palindromes

• 难度：1800
• 标签：dp、hashing、strings
• 链接：https://codeforces.com/problemset/problem/245/H
• 时间限制：5 seconds　内存限制：256 megabytes
• 出现位置：Day28-阶段模拟7-S T1-T3综合卷

中文题意

给定一个长度为 $|s|$ 的字符串 $s = s_1 s_2 \dots s_{|s|}$，仅由小写英文字母组成。另有 $q$ 个询问，每个询问由两个整数 $l_i, r_i$（$1 \le l_i \le r_i \le |s|$）描述。询问的答案为子串 $s[l_i \dots r_i]$ 中回文子串的个数。

字符串 $s[l \dots r] = s_l s_{l+1} \dots s_r$（$1 \le l \le r \le |s|$）是 $s = s_1 s_2 \dots s_{|s|}$ 的一个子串。

若字符串 $t$ 从左往右读和从右往左读相同，则称其为回文串。形式化地，若 $t = t_1 t_2 \dots t_{|t|} = t_{|t|} t_{|t|-1} \dots t_1$。

输入格式（中文）

第一行一个字符串 $s$（$1 \le |s| \le 5000$）。第二行一个整数 $q$（$1 \le q \le 10^6$），表示询问个数。接下来 $q$ 行为各询问，第 $i$ 行两个用空格分隔的整数 $l_i, r_i$（$1 \le l_i \le r_i \le |s|$），描述第 $i$ 个询问。

保证给定字符串仅由小写英文字母组成。

输出格式（中文）

输出 $q$ 个整数——各询问的答案，按输入中询问给出的顺序输出，数字之间用空白分隔。

样例

样例 1

输入：

caaaba
5
1 1
1 4
2 3
4 6
4 5

输出：

1
7
3
4
2