Friday, December 20, 2013

Find the longest palindrome substring

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

/*************************************************************
 * Function    : addSpecialChar
 * Input       : str
 * Output      : newStr
 * Description : This function gets a character array and
 *               inserts # in between each character and
 *               returns the new character array.
 *               Input : abcdef
 *               Output: #a#b#c#d#e#f#
 ************************************************************/
char *addSpecialChar(char *str)
{
  int index = 0;
  char *newStr = (char *) calloc (2*strlen(str)+1, 
                                  sizeof(char));
  if (NULL == newStr)
  {
    fprintf(stderr, 
            "[%s:%d] Memory allocation failed.", 
            __FUNCTION__, __LINE__);
    return NULL;
  }

  while ('\0' != *str)
  {
    newStr[index++] = '#';
    newStr[index++] = *str;
    str++;
  }

  newStr[index++] = '#';
  newStr[index] = '\0';
  return newStr;
}

/*************************************************************
 * Function    : getScore
 * Input       : str, score
 * Output      : maxScore
 * Description : This function calculates the number of 
 *               symmetric characters around each character
 *               in the given string and updates the score
 *               array. It returns the index of the max score
 *               from the score array.
 *               Input : #   a   #   a   #   b   #   c   #   b   #   a   #   
 *               Output: 0   1   2   1   0   1   0   5   0   1   0   1   0
 ************************************************************/
int getScore (char *str, int **score)
{
  int index = 1;
  int maxIndex = 0;
  int maxScore = 0;

  **score = 0;

  while ('\0' != str[index])
  {
    int leftindex = index - 1;
    int rightindex = index + 1;

    /* Calculate the score */
    int tmpScore = 0;
    for (;; leftindex--, rightindex++)
    {
      if (str[leftindex] != str[rightindex])
      {
        break;
      }
      if (leftindex == 0)
      {
        tmpScore++;
        break;
      }
      tmpScore++;
    }

    *((*score)+index) = tmpScore;
    if (maxScore < tmpScore)
    {
      maxScore = tmpScore;
      maxIndex = index;
    }

    /* The score on the left should be identical to the right
     * if the score at the new index is less than the difference
     * between score on the axis (current index) and the offset
     */
    int newIndex = 1;
    for (; newIndex < tmpScore; newIndex++)
    {
      if (*((*score)+index-newIndex) < *((*score)+index)-newIndex)
      {
        *((*score)+index+newIndex) = *((*score)+index-newIndex);
      }
      else
      {
        break;
      }
    }
    index = index + newIndex;

  }

  printf ("Max Index [%d]\n", maxIndex);
  return maxIndex;
}

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

  int *score = NULL;
  char *newStr = addSpecialChar (argv[1]);

  if (NULL != newStr)
  {
    score = (int *) calloc (strlen(newStr), sizeof (int));
    if (NULL == score)
    {
      fprintf(stderr, 
              "[%s:%d] Memory allocation failed.", 
              __FUNCTION__, __LINE__);
    }

    /* Print the actual string */
    printf ("%s\n%s\n", argv[1], newStr);

    int maxIndex = getScore (newStr, &score);

    /* Print the new string */
    for (int i=0; i<strlen(newStr); i++)
    {
      printf ("%-4c", newStr[i]); 
    }
    printf ("\n");

    /* Print the scores */
    for (int i=0; i<strlen(newStr); i++)
    {
      printf ("%-4d", score[i]); 
    }
    printf ("\n");

    /* Here is the longest palindrome */
    printf ("Longest Palindrome: ");
    int i = maxIndex/2 - score[maxIndex]/2;
    for (; i <= maxIndex/2 + score[maxIndex]/2; i++)
    {
      printf ("%c", argv[1][i]);
    }
    printf("\n");
  }

  return 0;
}
Output:
[COMMAND] ===>   ./logestPalindrome aabcba
aabcba
#a#a#b#c#b#a#
Max Index [7]
#   a   #   a   #   b   #   c   #   b   #   a   #   
0   1   2   1   0   1   0   5   0   1   0   1   0   
Longest Palindrome: abcba
-----------------------------------------------------------------------
[COMMAND] ===>   ./logestPalindrome aabcbabcbabcba
aabcbabcbabcba
#a#a#b#c#b#a#b#c#b#a#b#c#b#a#
Max Index [15]
#   a   #   a   #   b   #   c   #   b   #   a   #   b   #   c   #   b   #   a   #   b   #   c   #   b   #   a   #   
0   1   2   1   0   1   0   5   0   1   0   9   0   1   0   13  0   1   0   9   0   1   0   5   0   1   0   1   0   
Longest Palindrome: abcbabcbabcba
-----------------------------------------------------------------------
[COMMAND] ===>   ./logestPalindrome aabcbabcbaccba
aabcbabcbaccba
#a#a#b#c#b#a#b#c#b#a#c#c#b#a#
Max Index [11]
#   a   #   a   #   b   #   c   #   b   #   a   #   b   #   c   #   b   #   a   #   c   #   c   #   b   #   a   #   
0   1   2   1   0   1   0   5   0   1   0   9   0   1   0   5   0   1   0   1   0   1   2   1   0   1   0   1   0   
Longest Palindrome: abcbabcba
-----------------------------------------------------------------------
[COMMAND] ===>   ./logestPalindrome babcbabcbaccba
babcbabcbaccba
#b#a#b#c#b#a#b#c#b#a#c#c#b#a#
Max Index [11]
#   b   #   a   #   b   #   c   #   b   #   a   #   b   #   c   #   b   #   a   #   c   #   c   #   b   #   a   #   
0   1   0   3   0   1   0   7   0   1   0   9   0   1   0   5   0   1   0   1   0   1   2   1   0   1   0   1   0   
Longest Palindrome: abcbabcba
-----------------------------------------------------------------------
[COMMAND] ===>   ./logestPalindrome aaaaaaaaaaaaaaa
aaaaaaaaaaaaaaa
#a#a#a#a#a#a#a#a#a#a#a#a#a#a#a#
Max Index [15]
#   a   #   a   #   a   #   a   #   a   #   a   #   a   #   a   #   a   #   a   #   a   #   a   #   a   #   a   #   a   #   
0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  14  13  12  11  10  9   8   7   6   5   4   3   2   1   0   
Longest Palindrome: aaaaaaaaaaaaaaa
-----------------------------------------------------------------------
[COMMAND] ===>   ./logestPalindrome aaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaa
#a#a#a#a#a#a#a#a#a#a#a#a#a#a#a#a#
Max Index [16]
#   a   #   a   #   a   #   a   #   a   #   a   #   a   #   a   #   a   #   a   #   a   #   a   #   a   #   a   #   a   #   a   #   
0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16  15  14  13  12  11  10  9   8   7   6   5   4   3   2   1   0   
Longest Palindrome: aaaaaaaaaaaaaaaa
-----------------------------------------------------------------------
[COMMAND] ===>   ./logestPalindrome a
a
#a#
Max Index [1]
#   a   #   
0   1   0   
Longest Palindrome: a
Reference: http://leetcode.com/2011/11/longest-palindromic-substring-part-i.html