public Manacher(String s) {
		this.s = s.toCharArray();
		t = preprocess();
		p = new int[t.length];

		int center = 0, right = 0;
		for (int i = 1; i < t.length - 1; i++) {
			// equals to i' = center - (i-center)
			int mirror = 2 * center - i;

			//Optimization of pre-calculated palindrome in @center
			if (right > i)
				p[i] = Math.min(right - i, p[mirror]);

			// attempt to expand palindrome centered at i
			while (t[i + (1 + p[i])] == t[i - (1 + p[i])])
				p[i]++;

			// if palindrome centered at i expands past right,
			// adjust center based on expanded palindrome.
			if (i + p[i] > right) {
				center = i;
				right = i + p[i];
			}
		}
	}