最长回文子串

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1088

回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。
输入一个字符串Str，输出Str里最长回文子串的长度。

Input

输入Str（Str的长度 <= 1000)

Output

输出最长回文子串的长度L。

Input示例

daabaac

Output示例

5

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 Main {
	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;
	}
}

最长回文子串 V2

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1089

回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。
输入一个字符串Str，输出Str里最长回文子串的长度。

Input

输入Str（Str的长度 <= 100000)

Output

输出最长回文子串的长度L。

Input示例

daabaac

Output示例

5

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 Main {
	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;
	}
}