5658：CA Loves Palindromic

题目描述

CA loves strings, especially loves the palindrome strings.
One day he gets a string, he wants to know how many palindromic substrings in the substring $S[l,r]$.
Attantion, each same palindromic substring can only be counted once.

输入解释

First line contains $T$ denoting the number of testcases.
$T$ testcases follow. For each testcase:
First line contains a string $S$. We ensure that it is contains only with lower case letters.
Second line contains a interger $Q$, denoting the number of queries.
Then $Q$ lines follow, In each line there are two intergers $l,r$, denoting the substring which is queried.
$1 \le T \le 10,~1 \le length \le 1000,~1 \le Q \le 100000,~1 \le l \le r \le length$

输出解释

For each testcase, output the answer in $Q$ lines.

输入样例

1
abba
2
1 2
1 3

输出样例

2
3

提示

In first query, the palindromic substrings in the substring $S[1,2]$ are "a","b".
In second query, the palindromic substrings in the substring $S[1,2]$ are "a","b","bb".
Note that the substring "b" appears twice, but only be counted once.
You may need an input-output optimization.

来自杭电HDUOJ的附加信息

Recommend

wange2014

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 BestCoder Round #78 (div.2)

源链接： HDU-5658

最后修改于 2020-10-25T23:24:35+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
2000/1000MS(Java/Others)	262144/262144K(Java/Others)