palindrome.c

/*
 * Reads a word from standard input, and write the biggest palindrome it can
 * from that word and only by removing letters.
 * E.g. Biggest palindrome for "baobab" is "babab" (removing the "o").
 *
 * This is implemented using dynamic programming, that is searching the
 * longest common subsequence (O(n²) time and space complexity) between the word, 
 * and it's reverse:
 * i.e. LCS between "baobab" and "baboab"
 */
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_LEN 1000000

#define MAX(a, b) ((a) > (b) ? (a) : (b))

int
main(void)
{
	size_t **table;
	enum { kIgnoreA, kIgnoreB, kTake } **direction;
	char word[MAX_LEN];
	char palindrome[MAX_LEN];
	size_t len, i, j, pallen;

	if (fgets(word, MAX_LEN, stdin) == NULL) {
		fprintf(stderr, "Error when reading word\n");
		return 1;
	}
	len = strlen(word);
	word[len - 1] = 0;

	table = malloc(len * sizeof(size_t *));
	direction = malloc(len * sizeof(size_t*));
	for (i = 0; i < len; i++) {
		table[i] = malloc(len * sizeof(size_t));
		table[i][0] = 0;
		table[0][i] = 0;
		direction[i] = malloc(len * sizeof(size_t));
		direction[i][0] = kIgnoreB;
	}

	for (i = 1; i < len; i++) {
		for (j = 1; j < len; j++) {
			size_t same = !!(word[i - 1] == word[len - j - 1]);
			table[i][j] = table[i][j - 1];
			if (table[i - 1][j] > table[i][j]) {
				table[i][j] = table[i - 1][j];
				direction[i][j] = kIgnoreB;
			} else if (table[i - 1][j - 1] + same > table[i][j]) {
				table[i][j] = table[i - 1][j - 1] + same;
				direction[i][j] = kTake;
			} else {
				direction[i][j] = kIgnoreA;
			}
		}
	}

	pallen = table[len - 1][len - 1];
	palindrome[pallen--] = '\0';
	/* Let's read the word */
	i = j = len - 1;
	while (i > 0 || j > 0) {
		switch (direction[j][i]) {
		case kTake:
			assert(word[j - 1] == word[len - i - 1]);
			palindrome[pallen--] = word[len - i - 1];
			j--;
			i--;
			break;
		case kIgnoreA:
			i--;
			break;
		case kIgnoreB:
			j--;
			break;
		}
	}

	assert(pallen == -1);

	printf("Biggest palindrome: %lu: %s\n",
	       table[len - 1][len - 1],
	       palindrome);

	for (i = 0; i < len; i++)
		free(table[i]);
	free(table);

	return 0;
}