5062. Максимальный подпалиндром

Из данной строки удалите наименьшее количество символов так, чтобы получился палиндром (строка, одинаково читающаяся как справа налево, так и слева направо).

Вход. Непустая строка длиной не более 100 символов. Строка состоит только из заглавных латинских букв.

Выход. Выведите строку - палиндром максимальной длины, которую можно получить из исходной строки путем удаления некоторых букв. Если существует несколько таких палиндромов, выведите любой из них.

Пример входа	Пример выхода
WQWQEWAEQ	QWEWQ

РЕШЕНИЕ

динамическое программирование

наибольшая общая подпоследовательность

Анализ алгоритма

Рассмотрим исходную строку и ее реверс. Максимальный подпалиндром – это наибольшая общая подпоследовательность строки и ее реверса. Такой алгоритм работает за O(n²).

Пример

Найдем наибольшую общую подпоследовательность входной строки и ее реверса.

Реализация алгоритма

Объявим рабочие массивы. Входную строку содержим в x, ее реверс в y. Максимальный подпалиндром строим в res. Для динамики используем двумерный массив m.

#define MAX 110

string x, y, res;

int m[MAX][MAX];

Читаем входную строку. Находим ее реверс в y. В начало строк x и y поставим пробел.

cin >> x; y = x;

reverse(y.begin(), y.end());

x = ' ' + x; y = ' ' + y;

len = x.size();

Запускаем алгоритм вычисления наибольшей общей подпоследовательности.

memset(m,0,sizeof(m));

for(i = 1; i < len; i++)

for(j = 1; j < len; j++)

if (x[i] == y[j]) m[i][j] = 1 + m[i-1][j-1];

else m[i][j] = max(m[i-1][j],m[i][j-1]);

По массиву m восстанавливаем НВП.

i = j = len - 1;

res = "";

while(m[i][j] > 0)

{

if (x[i] == y[j])

{

res += x[i];

i--; j--;

}

else if (m[i-1][j] > m[i][j-1]) i--; else j--;

}

Выводим искомый максимальный подпалиндром.

cout << res << endl;

Реализация алгоритма – динамическое программирование

Объявим рабочий массив dp.

#define MAX 101

int dp[MAX][MAX];

Функция f вычисляет длину палиндрома наибольшей длины, который можно получить из строки s[i .. j] и запоминает это значениек в dp[i][j].

int f(int i, int j)

{

if (i > j) return 0;

if (i == j) return 1;

if (dp[i][j] != -1) return dp[i][j];

if (s[i] == s[j])

return dp[i][j] = f(i + 1, j - 1) + 2;

else

return dp[i][j] = max(f(i + 1, j), f(i, j - 1));

}

Функция print выводит палиндром наибольшей длины, который можно получить из строки s[i .. j]. Используются ранее вычиленные значения массива dp.

void print(int i, int j)

{

if (i > j) return;

if (i == j)

{

cout << s[i];

return;

}

if (s[i] == s[j])

{

cout << s[i];

print(i + 1, j - 1);

cout << s[j];

}

else

{

if (dp[i + 1][j] > dp[i][j - 1])

print(i + 1, j);

else

print(i, j - 1);

}

}

Основная часть программы. Читаем входную строку s.

cin >> s;

memset(dp, -1, sizeof(dp));

Вычисляем и выводим ответ.

f(0, s.size());

print(0, s.size());

cout << endl;