FInding longest palindromic substring using DP. Complexity : O(n^2) Space complexity: O(n^2)

longest_pali_string.cpp

/*
 * Longest palindromic string
 * This is 0n^2 complexity
 * space complexity is also 0n^2
 * Although a solution with 0n^2 with constant space is also possible */

string longestPalindrome(char *A) {
    int **table;
    int n = A.length();
    int i, j, len;
    int start = 0, max_len = 1;
    
    table = (int**) malloc (n * sizeof(int*));
    
    for (i=0; i< n; i++)
        table[i] = (int*) malloc (n * sizeof(int));
    
    // Initialise table
    for (i=0; i<n; i++)
        for (j=0; j<n; j++)
            table[i][j]=0;
            
    // length 1: single char    
    for (i=0; i< n; i++) {
        table[i][i] = 1;
    }
    
    // length 2
    for (i=0; i< n; i++) {
        if (A[i] == A[i+1]) {
            table[i][i+1] = 1;
            start = i;
            max_len = 2;
        }
    }
    
    // length 3 and higher
    for (len=3; len <= n; len++) {
        for (i=0; i <= (n-len ); i++) {
            j = i + len - 1;
            if ((A[i] == A[j]) && table[i+1][j-1]) {
                table [i] [j] = 1;
                // in case of multiple possibilities we want the first
                if (len > max_len) {
                    start = i;
                    max_len = len;
                }
            }
        }
    }
    
    return A.substr (start, max_len);
}

longest_pali_string_optimised.c

/* THE IDEA :
 * There are 2n-1 centers possible
 * for a palindromic substring in a string of length n
 *
 * And we need __order_of__ n iterations to traverse the string
 * for each center
 *
 * Hence this problem has been solved in O(n^2) complexity and constant extra space
 */

// THE SOLUTION:

/*
 * Helper methods */

// Given center point, it finds the max length of palindromic sub-string possible
void traverse (char *A, int left, int right, int *__max_begin, int *__max_len) {
    int rightmost = strlen (A) - 1;
    int leftmost = 0;
    int len = 0;
    
    if ((left > right) || (left < leftmost) || (right > rightmost)) {
        *__max_len = 0;
        *__max_begin = -1;
        return;
    }
    
    if (left == right) {
        len ++;
        left --;
        right ++;
    }
    
    while ((left >= leftmost) && (right <= rightmost) && (A[left] == A[right])) {
        left --;
        right ++;
        len += 2;
    }
    
    *__max_len = len;
    *__max_begin = (left + 1);
}

// Create a sub-string using a string
char *__substr (char *A, int begin, int len) {
    char *res;
    int i;
    
    res = (char *) malloc ((len+1) * sizeof (char));
    
    for (i=0; i<len; i++) {
        res [i] = A[begin];
        begin ++;
    }
    
    // null terminate the string
    res [len] = '\0';
    
    return res;
}

/*
 * Main method */
char* longestPalindrome(char* A) {
    /*
     * Call traverse for all the 2n-1 possible centers */
    
    int centers =  2 * strlen (A) - 1;
    
    int index, len, max_len, begin, max_begin, left, right;
    max_begin = 0;
    max_len = 1;
    
    for (index=0; index< centers; index++) {
        left = floor (index/2.0);
        right= ceil (index/2.0);
        traverse (A, left, right, &begin, &len);
        
        if (len > max_len) {
            max_len = len;
            max_begin = begin;
        }
    }
    
    return __substr (A, max_begin, max_len);
}