L2-008. 最长对称子串
时间限制
100 ms
内存限制
65536 kB
代码长度限制
8000 B
判题程序
Standard
作者
陈越
对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定"Is PAT&TAP symmetric?"，最长对称子串为"s PAT&TAP s"，于是你应该输出11。
输入格式：
输入在一行中给出长度不超过1000的非空字符串。
输出格式：
在一行中输出最长对称子串的长度。
输入样例：Is PAT&TAP symmetric?输出样例：
11
import java.util.Scanner;
public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); String s = sc.nextLine();System.out.println(getPalindromeLength(s));}public static int getPalindromeLength(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]);}//寻找更大半径//三个条件 1:中心-半径>=0 2:中心+半径<字符串长度(中心+半径<=length-1) 3:字符串关于中心对称点相同//符合条件的话，半径自加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){if(r>maxLength){maxLength = r;}}return maxLength-1 ;}
}因为