最长回文子串

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 {
		StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		while (in.nextToken() != StreamTokenizer.TT_EOF) {
			String s1 = in.sval;
			out.println(Manacher(s1));
		}
		out.flush();
	}

	static int Manacher(String str) {
		String s = "$#";
		for (int i = 0; i < str.length(); i++) {
			s += str.charAt(i) + "#";
		}
		int max = 0;
		int id = 0;
		int[] p = new int[s.length()];
		for (int i = 0; i < s.length(); i++) {
			int maxLen = p[id] + id;
			if (maxLen > i) {
				p[i] = Math.min(p[2 * id - i], maxLen - i);
			}
			while (i + p[i] < s.length() && i - p[i] >= 0 && s.charAt(i - p[i]) == s.charAt(i + p[i])) {
				p[i]++;
			}
			if (maxLen < i + p[i]) {
				id = i;
			}
			max = Math.max(max, p[i]);
		}
		return max - 1;
	}
}