UVA 11475 'Extend to Palindrome

main.cpp

#include <iostream>
#include <cstring>

using namespace std;

#define MAX_LEN 100000

char buffer[2*MAX_LEN + 2];
char* original;
int originalLength;
char* reversed;
char* composed;
int composedLength;
int b[2*MAX_LEN + 10];

void prependReversed() {
	for (int i = 0, j = originalLength - 1; i < originalLength; ++i, --j) {
		reversed[j] = original[i];
	}
}

int kmpPreprocess() {
	int i = 0, j = -1; b[0] = -1;
	while (i < composedLength) {
		while (j >= 0 && composed[i] != composed[j]) j = b[j];
		i++; j++;
		b[i] = j;
	}

	return min(b[composedLength], composedLength / 2);
}

void printTable() {
	cout << "Preprocessing table: " << endl;
	for (int i = 0; i < composedLength; ++i) cout << composed[i] << '\t';
	cout << endl;
	for (int i = 0; i < composedLength + 1; ++i) cout << b[i] << '\t';
	cout << endl;
}

int main(int argc, char* argv[]) {
	original = &buffer[MAX_LEN + 1];
	while( cin.getline(original, MAX_LEN + 1) ) {
		buffer[MAX_LEN] = '#'; // separator to avoid overlapping pre- and suffixes
		originalLength = strlen(original);
		reversed = composed = &buffer[MAX_LEN - originalLength];
		prependReversed();
		composedLength = 2*originalLength + 1;

//		cout << "Composed: " << composed << endl; 
		int prefixLength = kmpPreprocess();
//		printTable();
		buffer[MAX_LEN] = '\0';

		cout << original;
		cout << &composed[prefixLength] << endl;

		memset(buffer, 0, sizeof buffer);
	}
	return 0;
}