Задача
Из данной строки удалите наименьшее количество символов так, чтобы получился палиндром (строка, одинаково читающаяся как справа налево, так и слева направо).
Входные данные:
Непустая строка длиной не более [latex]100[/latex] символов. Строка состоит только из заглавных латинских букв.
Выходные данные:
Вывести строку-палиндром максимальной длины, которую можно получить из исходной вычёркиванием нескольких букв. При наличии нескольких решений необходимо вывести одно (любое) из них.
Тесты
| № | Входные данные | Выходные данные |
| 1 | QWEERTYY | YY |
| 2 | QWEERT | EE |
| 3 | BAOBAB | BAOAB |
| 4 | ABCDCBA | ABCDCBA |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include <iostream> #include <string> #include <algorithm> using namespace std; string **dp; int main() { string s1,s2; long long i,j; cin>>s1; s2=s1; long long m=s1.size()+1; reverse(s2.begin(),s2.end()); dp=new string* [m]; for(i=0;i<m;i++)dp[i]=new string [m]; for(i=1;i<m;i++){ for(j=1;j<m;j++){ if(s1[i-1]==s2[j-1])dp[i][j]=dp[i-1][j-1]+s2[j-1]; else{ if(dp[i-1][j].size()>dp[i][j-1].size())dp[i][j]=dp[i-1][j]; else dp[i][j]=dp[i][j-1]; } } } cout<<dp[m-1][m-1]; return 0; } |
Засчитанное решение на e-olymp.
Решение
Так как палиндром читается одинаково как справа налево, так и слева направо, то максимальным подпалиндромом будет наибольшая общая подстрока двух строк: исходной строки [latex]s_1[/latex] и этой же строки, но записанной в обратном порядке [latex]s_2[/latex] (как, если бы мы её читали справа налево). Для нахождения их наибольшей общей подстроки следует заполнить таблицу [latex]D[/latex] размером [latex] (n+1)\times(n+1) [/latex], где [latex]n[/latex]-длина строки. Заполнять таблицу будем методом аналогичным поиску длины наибольшей общей подстроки, но в каждой ячейке [latex]D_{i j}[/latex] таблицы будем хранить наибольшую подстроку строки, содержащей только первые [latex]i[/latex] символов [latex]s_1[/latex], и строки, содержащей только [latex]j[/latex] первых символов [latex]s_2[/latex]. В ячейках [latex]D_{0 j}[/latex] и [latex]D_{i 0}[/latex] будем хранить пустые строки. Если [latex]i[/latex]-й символ строки [latex]s_1[/latex] равен [latex]j[/latex]-ому символу строки [latex]s_2[/latex], то в ячейку [latex]D_{i j}[/latex] запишем конкатенацию строки из ячейки [latex]D_{i-1 j-1}[/latex] и данного символа. Иначе в ячейке [latex]D_{i j}[/latex] будем хранить наибольшую из строк [latex]D_{i-1 j}[/latex] и [latex]D_{i j-1}[/latex]. Таким образом в ячейке [latex]D_{n n}[/latex] будет хранится наибольший подпалиндром исходной строки.
Зачтено