题解 | #最长回文子串#

public class Main{
	public static void main(String[] args) {		//最长回文子串
		Scanner sc = new Scanner(System.in);
		String str = sc.nextLine();
		int n = str.length();
		int[] f = new int[n+1];
		/*
		 * f[i]的含义为：以str第i个字母结尾的回文串的最大长度。
		 * 分情况讨论：
		 * 1. if: f[i-1]<i-1且str[i]==str[i-1-f[i-1]]:  f[i]=f[i-1]+2;每次最多增加两个，即头尾增加两个相同的字符，这时要关注不要数组越界
		 * 2. else if: str[i]==str[i-1]且（ f[i-1]-f[i-2]==1 或 f[i-1]==1）:           f[i]=f[i-1]+1;每次增加一个，即尾部增加一个，只有在当前整个回文串都是同一个字符的情况下才会出现增加一个的情况。
		 * 3. else: 									f[i]=1;无法与前面的字符构成回文字符，只能以自己为一个单独的回文字符。
		 * 初始条件：
		 * f[0]=0;
		 * f[1]=1;
		 * */
		char[] arr = str.toCharArray();
		int max = 0;
		for(int i=0;i<=n;i++){
			if(i==0 || i==1){
				f[i] = i;
			}
			else{
				if(f[i-1]<i-1 && arr[i-1]==arr[i-2-f[i-1]]){
					f[i]=f[i-1]+2;
				}
				else if(arr[i-1]==arr[i-2] && (f[i-1]==f[i-2]+1||f[i-1]==1)){
					f[i]=f[i-1]+1;
				}
				else{
					f[i]=1;
				}
			}
			if(f[i]>max){
				max = f[i];
			}
			//if(i>0)System.out.println(i+" "+arr[i-1]+" "+f[i]);
		}
		System.out.println(max);
	}
}