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

char* input = "FourscoreandsevenyearsagoourfaathersbroughtforthonthiscontainentanewnationconceivedinzLibertyanddedicatedtothepropositionthatallmenarecreatedequalNowweareengagedinagreahtcivilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth";

char* sub_seq(const char* source, int start, int end)
{
    char* result;
	int i;
	result = malloc((end - start + 1) * sizeof(char));
	for (i = 0; i < end - start; ++i)
	{
		result[i] = source[i + start];
 	}
 	result[end - start] = '\0';
 	return result;
}

char* seek_palindrome(const char* input)
{
	char* answer;
	answer = malloc(sizeof(char));
	answer[0] = '\0';

	int len, i, j, k;
	len = strlen(input);

	for (i = 1; i < len - 1; ++i)
	{
		for (j = i - 1, k = i + 1; j >= 0 && k < len; --j, ++k)
		{
			if (input[j] == input[k])
			{
				char* palindrome = sub_seq(input, j, k + 1);
				if (strlen(palindrome) > strlen(answer))
				{
					free(answer); answer = NULL;
					answer = palindrome;
				}
				else
				{
					free(palindrome);
				}
			}
			else
			{
				break;
			}
		}
	}

	for (i = 1; i < len - 1; ++i)
	{
		for (j = i, k = i + 1; j >= 0 && k < len; --j, ++k)
		{
			if (input[j] == input[k])
			{
				char* palindrome = sub_seq(input, j, k + 1);
				if (strlen(palindrome) > strlen(answer))
				{
					free(answer); answer = NULL;
					answer = palindrome;
				}
				else
				{
					free(palindrome);
				}
			}
			else
			{
				break;
			}
		}
	}
	return answer;
}

int main(int argc, char* argv[])
{
	clock_t t;
	char* result;
	t = clock();
	result = seek_palindrome(input);
	t = clock() - t;

	printf("The longest palindrome is '%s' calculated in %f seconds\n", result, ((float) t) / CLOCKS_PER_SEC);
	free(result); result = NULL;
	return EXIT_SUCCESS;
}