最大回文算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44



public class Solution {

	static Solution sa = new Solution();

	char[] ss;
	int left = 0, max = 1;

	public String longestPalindrome(String s) {
		ss = s.toCharArray();
		if (ss.length < 1) return "";
		for (int i = 0; i < ss.length; i++) {
			i = update(i);
		}
		return s.substring(left, left + max);
	}

	private int update(int index) {
		int ll = index, rr = index;
		// ()->rr || []->ll
		// [ll,rr]->(a)aa    rr=index
		// [a](a)a           rr=index+1 传递
		// [a]a(a)           rr=index+2
		while (rr + 1 < ss.length && ss[rr] == ss[rr + 1]) {
			rr++;
		}
		int temp = rr;
		// ll-1 | rr+1，下一个匹配
		// [ll-1][a]a(a)(rr+1) rr=index+2
		while (rr + 1 < ss.length && ll - 1 >= 0 && ss[rr + 1] == ss[ll - 1]) {
			rr++;
			ll--;
		}
		if (rr - ll + 1 > max) {
			max = rr - ll + 1; // 计算长度
			left = ll; // 记录开始位置
		}
		return temp;
	}

	public static void main(String[] args) {
		System.out.println(sa.longestPalindrome("babad"));
	}

}