#include <iostream>
using namespace std;

pair<int, int> manacher(string s) {
	// assuming string is in the format of #s[1]#s[2]#...#s[n]# 
	// format with length larger than 3 (original unpadded string
	// has more than one char).

	// preparation phase
	int* p = new int[s.size()]();
	p[0] = 1; p[1] = 2;
	int mx = 3;	// mx: store the index immediate after current
	            //longest palindrome
	int ind = 1; // ind: store current longest palindrome
	             //center index.

	for (int i = 2; i < s.size(); i++) {
		// step1: precalculate p[i]
		if (i < mx) {
			int mirrorPi = p[2 * ind - i];
			int safePi = mx - i;
			p[i] = mirrorPi < safePi ? mirrorPi : safePi;
		}
		else {
			p[i] = 1;
		}

		// step2: expand
		while (i + p[i] < s.size() \
			   && i - p[i] >= 0 \
			   && s[i + p[i]] == s[i - p[i]])
			p[i]++;

		// step3: update mx and ind
		if (i + p[i] > mx) {
			mx = i + p[i];
			ind = i;
		}
	}

	return make_pair(p[ind], ind);
}


int main() {
	string s = "#1#2#2#1#2#3#2#1#";

	pair<int, int> p = manacher(s);
	cout << "radius is " << p.first << ", center at " << p.second << endl;

 	return 0;
}