Manacher Algorithm

#include <iostream>
#include <vector>
#include <boost/shared_ptr.hpp>
using namespace std;

// Data Structure
typedef struct ManacherAlgorithmDataUnit
{
	char str;
	int  maxPalindromeNum;
}DataUnit;

typedef vector< shared_ptr<DataUnit> > DataList;

// Function
static inline int min(int compare1, int compare2)
{
	return (compare1 > compare2 ? compare1 : compare2);
}

int ManacherAlgorithm(DataList& list)
{
	int rightestPalindromeIndex = 0;
	int rightestPalindromeCenterIndex = 0;
	int maxPalindromeIndex = 0;

	for (int dataIndex = 0; dataIndex < list.len(); ++dataIndex) {
		// If the rightest palindrome index is bigger than the index, then we can use the index matched left index‘s max palindrome value.
		strList[dataIndex]->maxPalindromeNum = (rightestPalindromeIndex > dataIndex) ? min(strList[2 * rightestPalindromeCenterIndex - dataIndex], rightestPalindromeIndex - dataIndex) : 1;

		// If the matched index‘s palindrome size is bigger than the index to center index, it mean the index‘s size must be rightest inde minus center index.
		// Because if the size is bigger than it, the center index‘s palindrome size should be longer.
		if (strList[2 * rightestPalindromeCenterIndex - dataIndex]->maxPalindromeNum > rightestPalindromeIndex - dataIndex) {
			strList[dataIndex]->maxPalindromeNum = rightestPalindromeIndex - dataIndex;
		}
		else {
			// search current index to be the center value‘s max palindrome‘s rightest index.
			while (strList[dataIndex + strList[dataIndex]->maxPalindromeNum] == strList[dataIndex - strList[dataIndex]->maxPalindromeNum]) ++strList[dataIndex]->maxPalindromeNum;
		}

		// update the palindrome‘s rightest index
		if (dataIndex + strList[dataIndex]->maxPalindromeNum > rightestPalindromeIndex) {
			rightesPalindromeCenterIndex = dataIndex;
			rightestPalindromeIndex = dataIndex + strList[dataIndex]->maxPalindromeNum;
		}

		// update the max palindrome‘s index
		if (strList[maxPalindromeIndex]->maxPalindromeNum < strList[dataIndex]->maxPalindromeNum) maxPalindromeIndex = dataIndex;
	}
}

int main()
{
	DataList strList;
	int      listLen = 0;
	int      maxPalindromeIndex = 0;
	string   checkString = "";

	cin >> listLen;
	cout << "Input List Len: " << listLen << endl;

	for (int strIndex = 0; strIndex < listLen; ++strIndex) {
		// Insert ‘#‘ to make the string list to odd number.
		shared_ptr<DataUnit> data(new DataUnit);
		data->str = ‘#‘;
		data->maxPalindromeNum = 1;
		strList.push_back(data);

		// Insert the real str to the string list
		shared_ptr<DataUnit> realData(new DataUnit);
		realData->cin.getchar();
		realData->maxPalindromeNum = 1;
		strList.push_back(realData);

		checkString += realData->str;
	}

	// Insert a ‘#‘ to the end of the string
	shard_ptr<DataUnit> data(new DataUnit);
	data->str = ‘#‘;
	data->maxPalindromeNum = 1;
	strList.push_back(data);

	cout << "Input Checking String: " << checkString.c_str() << endl;

	// Doing the ManacherAlgorithm
	maxPalindromeIndex = ManacherAlgorithm(strList);

	cout << "The max PalindromeIndex: " << maxPalindromeIndex << endl;
	cout << "The max PalindromeNum: " << strList[maxPalindromeIndex]->maxPalindromeNum - 1 << endl;
	cout << "The max Palindrome: ";

	if (strList[maxPalindromeIndex]->maxPalindromeNum - 1 == 0) {
		cout << "none" << endl;
	}
	else {
		for (int strIndex = maxPalindromeIndex / 2 - (strList[maxPalindromeIndex]->maxPalindromeNum - 1) / 2; 			strIndex < maxPalindromeIndex / 2 + (strList[maxPalindromeIndex]->maxPalindromeNum - 1) / 2; 			++strIndex) {
			cout << checkString[strIndex];
		}

		cout << endl;
	}

	return 0;
}