最长回文子串 v2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class  {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		String s1 = in.readLine();
		out.println(Manacher(s1));
		out.flush();
	}

	static int Manacher(String str) {
		StringBuilder newStr = new StringBuilder();
		newStr.append('#');
		for (int i = 0; i < str.length(); i++) {
			newStr.append(str.charAt(i));
			newStr.append('#');
		}
		int[] rad = new int[newStr.length()];
		int right = -1;
		int id = -1;
		for (int i = 0; i < newStr.length(); i++) {
			int r = 1;
			if (i <= right) {
				r = Math.min(rad[id] - i + id, rad[2 * id - i]);
			}
			while (i - r >= 0 && i + r < newStr.length() && newStr.charAt(i - r) == newStr.charAt(i + r)) {
				r++;
			}
			if (i + r - 1 > right) {
				right = i + r - 1;
				id = i;
			}
			rad[i] = r;
		}
		int maxLength = 0;
		for (int r : rad) {
			maxLength = Math.max(r, maxLength);
		}
		return maxLength - 1;
	}
}