题目解析
给定字符串 求出最长回文字符串的长度
解题思路
马拉车板子题
代码
import java.io.*;
import java.math.*;
import java.util.*;
public class Main
{
static String solve(String s)
{
// 插入原来的字符串的长度 在插入一个字符 保证最后为奇数个
StringBuilder t = new StringBuilder("$#");
for (int i = 0; i < s.length(); i++)
t.append(s.charAt(i) + "#");
t.append("@");
// p[i] 表示 以 t[i] 为中心的最长回文字符串
int p[] = new int[t.length() + 10];
// 回文子串的右边界 和 中心位置
int mx = 0, idx = 0;
// 中心点 和 最长长度的左半边
int cen = 0, len = 0;
for (int i = 1; i < t.length() - 1; i++)
{
// 如果i在idx为中心，p[i]为半径的范围内，那么i的对称点就是 j = 2 * idx - 1
// 所以i的回文半径至少是对称点p[j]的半径，或者是要撑破，最少是i到mx距离
// 否则i比mx大 p[i] = 1
p[i] = 1;
if (mx > i)
p[i] = Math.max(p[2 * idx - i], mx - i);
// i - p[i] >= 1 保证左边不越界
// i + p[i] < t.length() - 1 保证右边不越界
// 并且左右两个字符相同
while ((i - p[i] >= 1 && i + p[i] < t.length() - 1) && (t.charAt(i - p[i]) == t.charAt(i + p[i])))
p[i]++;
if (mx < p[i] + i)
{
mx = p[i] + i;
idx = i;
}
// 找到更长的半径
if (len < p[i])
{
len = p[i];
cen = i;
}
}
return s.substring((cen - len) / 2, (cen - len) / 2 + len - 1);
}
public static void main(String[] args)
{
String s = sc.nextLine();
out.println(solve(s).length());
out.flush();
out.close();
}
static Scanner sc = new Scanner(System.in);
static PrintWriter out = new PrintWriter(System.out);
}