/* Problem 2--Making Pals
   This was handled by checking internal palindromes within the string
   and building the new string around this palindrome. */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main (int argc, char **argv);
void Process (FILE *out, char *nstr, int cs);
int IsPalindrome (char *nstr, int i, int j);

int main (int argc, char **argv) {

  int cs;
  FILE *in, *out;
  char nstr[15];

 in = fopen ("prob2.in","r");
 out = fopen ("prob2.out","w");
 for (cs=1;fgets(nstr,15,in),nstr[(strlen (nstr)-1)]=0,nstr[0]>0;cs++)
   /* Read in string */
  Process (out,nstr,cs); /* Process the data case */
 fclose (in);
 fclose (out);
 return EXIT_SUCCESS;
}

/* Process takes string nstr and computes and prints the answer for that
   case. */

void Process (FILE *out, char *nstr, int cs) {

  int cost, i, j, length, left, right, newcost, newlength;

 cost = strlen (nstr) - 1; /* maximum possible cost */
 length = 2*strlen (nstr) - 1; /* maximum possible length */
               /* Go through string looking for maximal palindromes */
 for (i=0;i<(int)strlen (nstr);i=j) {/*left end of maximal palindrome */
  j = i;
  for (j=i;j<(int)strlen (nstr) && IsPalindrome (nstr,i,j);j++);
                /* right end of maximal palindrome */
  left = i; /* compute new cost and length of string built around */
  right = strlen(nstr) - j; /* this internal palindrome */
  newcost = left+right;
  newlength = strlen (nstr) + abs(left-right);
  if (newcost < cost || (newcost==cost && newlength > length)) {
   cost = newcost; /* If this gives a better answer, use it. */
   length = newlength;
  }
 }
 fprintf (out,"Case %d, sequence = %s, cost = %d, length = %d\n", cs,
              nstr,cost,length);
}

/* IsPalindrome returns true if nstr is palindromic between positions i
   and j. */

int IsPalindrome (char *nstr, int i, int j) {

  char A[10], B[10];
  int k;

 for (k=0;k<10;k++) { /* initialize strings */
  A[k] = B[k] = 0;
 }
 k = i; /* build two strings, forward and backward */
 for (k=i;k<=j;k++)
  A[k-i] = B[j-k] = nstr[k];
 return strcmp (A,B) == 0; /* see if strings are equal */
}