Задана строка s = s1s2... s|s| длины |s|, состоящая из строчных букв латинского алфавита. А также q запросов, каждый запрос описывается
двумя целыми числами li, ri (1 ≤ li ≤ ri ≤ |s|). Ответ на запрос – количество
подстрок строки s[li... ri], которые являются
палиндромами.
Строка s[l...
r] = slsl + 1... sr (1 ≤ l ≤ r ≤ |s|) называется подстрокой строки s = s1s2...
s|s|.
Строка t
называется палиндромом, если она одинаково читается как слева направо, так и
справа налево. Формально, если t = t1t2... t|t| = t|t|t|t-1|... t1.
Вход. В первой строке записана строка s (1 ≤ |s| ≤ 5000).
Во второй строке записано единственное целое число q (1 ≤ q ≤ 106)
– количество запросов. В следующих q
строках записаны сами запросы. В i-той
из этих строк записаны два целых числа через пробел li, ri
(1 ≤ li ≤ ri ≤ |s|)
– описание i -го запроса.
Гарантируется, что заданная строка состоит только из
строчных букв латинского алфавита.
Выход. Выведите q целых чисел – ответы на запросы.
Ответы на запросы выводите в том порядке, в котором запросы заданы во входных
данных. Выведенные числа разделяйте пробельными символами.
Пример входа
caaaba
5
1 1
1 4
2 3
4 6
4 5
Пример
выхода
1
7
3
4
2
динамическое программирование - палиндромы
Пусть s – входная
строка. Реализуем функцию IsPal(i, j), возвращающую 1 если подстрока
является палиндромом и 0 иначе. При этом
·
IsPal(i, j) = 1, если IsPal(i + 1, j – 1) = 1 и si = sj;
·
IsPal(i, j) = 0 иначе;
Пусть f(i, j)
возвращает количество палиндромов в подстроке si... sj. Тогда
f(i, j) = f(i + 1, j) + f(i, j – 1) – f(i + 1, j – 1) + IsPal(i, j)
Реализация алгоритма
#include <cstdio>
#include <algorithm>
#define MAX 5010
using namespace
std;
int dp[MAX][MAX], pal[MAX][MAX];
char s[MAX];
int i, j, k, q;
int IsPal(int
i, int j)
{
if (i >= j) return
pal[i][j] = 1;
if (pal[i][j] != -1) return
pal[i][j];
return pal[i][j] = (s[i] == s[j]) &&
IsPal(i+1,j-1);
}
int f(int
i, int j)
{
if (i == j) return 1;
if (i > j) return
0;
if (dp[i][j] != -1) return
dp[i][j];
return dp[i][j] = f(i+1,j) + f(i,j-1) - f(i+1,j-1) +
IsPal(i,j);
}
int main(void)
{
gets(s+1);
memset(pal,-1,sizeof(pal));
memset(dp,-1,sizeof(dp));
scanf("%d",&q);
for(k = 0; k < q; k++)
{
scanf("%d %d",&i,&j);
printf("%d\n",f(i,j));
}
return 0;
}