10453. Make Palindrome

 

By definition palindrome is a string which is not changed when reversed. “MADAM” is a nice example of palindrome. It is an easy job to test whether a given string is a palindrome or not. But it may not be so easy to generate a palindrome.

Here we will make a palindrome generator which will take an input string and return a palindrome. You can easily verify that for a string of length n, no more than (n – 1) characters are required to make it a palindrome. Consider “abcd” and its palindrome “abcdcba” or “abc” and its palindrome “abcba”.

But life is not so easy for programmers!! We always want optimal cost.

And you have to find the minimum number of characters required to make a given string to a palindrome if you are allowed to insert characters at any position of the string.

 

Input. Each input line consists only of lower case letters. The size of input string will be at most 1000. Input is terminated by EOF.

 

Output. For each input print the minimum number of characters and such a palindrome separated by one space in a line. There may be many such palindromes. Any one will be accepted.

 

Sample Input

abcd

aaaa

abc

aab

abababaabababa

pqrsabcdpqrs
 

Sample Output

3 abcdcba

0 aaaa

2 abcba

1 baab

0 abababaabababa

9 pqrsabcdpqrqpdcbasrqp

 

 

РЕШЕНИЕ

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

 

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

Пусть s = s1s2…sn – строка, которую за наименьшее количество операций можно превратить в палиндром. Для преобразования строки в палиндром разрешается вставлять буквы в любые позиции.

Пусть Solve(i, j) возвращает наименьшее количество букв, которое следует вставить в подстроку si…sj чтобы сделать ее палиндромом. Рассмотрим варианты ее вычисления:

·         если s[i] = s[j], то Solve(i, j) = Solve(i + 1, j – 1);

·         если в конце подстроки si…sj поставить символ si получив таким образом si…sjsi, то далее в палиндром следует преобразовать подстроку si+1…sj и Solve(i, j) = Solve(i + 1, j) + 1;

·         если в начале подстроки si…sj поставить символ sj получив таким образом sjsi…sj, то далее в палиндром следует преобразовать подстроку si…sj-1 и Solve(i, j) = Solve(i, j – 1) + 1;

Остается из трех вариантов выбрать тот, который дает в результате наименьшее значение для Solve(i, j).

Для восстановления палиндрома нам следует запоминать операции, проведенные при его получении. Для этого воспользуемся массивом prev. Пусть prev[i][j] содержит:

·         1, если s[i] = s[j] и Solve(i, j) = Solve(i + 1, j – 1);

·         2, если Solve(i, j) = Solve(i + 1, j) + 1;

·         3, если Solve(i, j) = Solve(i, j – 1) + 1;

Генерируем по массиву prev искомый палиндром наименьшей длины.

 

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

 

#include <cstdio>

#include <cstring>

#define MAX 1001

#define INF 0x3F3F3F3F

using namespace std;

 

char s[MAX], pal[2*MAX];

int dp[MAX][MAX], prev[MAX][MAX];

int res;

 

void Print(int i, int j, int i1, int j1)

{

  if (i > j) return;

  if (prev[i][j] == 1)

  {

    pal[i1] = pal[j1] = s[i];

    Print(i+1,j-1,i1+1,j1-1);

  }

 

  if (prev[i][j] == 2) // insert i

  {

    pal[i1] = pal[j1] = s[i];

    Print(i+1,j,i1+1,j1-1);

  }

 

  if (prev[i][j] == 3) // delete j

  {

    pal[i1] = pal[j1] = s[j];

    Print(i,j-1,i1+1,j1-1);

  }

}

 

int Solve(int i, int j)

{

  if(i > j) return 0;

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

 

  // s[i] = s[j]

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

  {

    dp[i][j] = Solve(i+1,j-1);

    prev[i][j] = 1; // 1

  }

 

  // insert at position i

  int temp = Solve(i+1,j) + 1;

  if(temp < dp[i][j])

  {

    dp[i][j] = temp;

    prev[i][j] = 2; // INSERT

  }

 

  // delete from position j

  temp = Solve(i,j-1) + 1;

  if(temp < dp[i][j])

  {

    dp[i][j] = temp;

    prev[i][j] = 3; // DELETE

  }

  return dp[i][j];

}

 

int main(void)

{

  while(gets(s))

  {

    memset(dp,0x3F,sizeof(dp));

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

    memset(pal,0,sizeof(pal));

    res = Solve(0,strlen(s)-1);

    Print(0,strlen(s)-1,0,strlen(s)+res-1);

    printf("%d %s\n",res,pal);

  }

}