经典算法-求解最长回文子串问题（返回所有符合条件的子串集合）Java版题解

本文主要是介绍经典算法-求解最长回文子串问题（返回所有符合条件的子串集合）Java版题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

求解最长回文子串，有一个中心扩展算法思想。
模版如下：

	/*算法思想很好理解，如果一个元素的左右两端也相等，那么就将左指针和右指针向两端移动一位，再来比较当前左右指针的元素是否还相等，如果还相等，则继续移动，否则跳出循环。最后返回能匹配到的回文字符串长度*/private static int expandAroundCenter(String s, int left, int right) {int L = left, R = right;while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {L--;R++;}return R - L - 1;//跳出循环时，R和L都+1了，我们要去上一次循环时候的R0和L0，即R0=R-1和L0=L-1，计算字符串长度为R0-L0+1，所以返回R-L-1}

import java.util.ArrayList;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String s=sc.next();//若字符串为空，则返回""if (s == null || s.length() ==0)System.out.println("");int start = 0, end = 0;ArrayList<int []> res=new ArrayList<>();int maxLen=0;for (int i = 0; i < s.length(); i++) {int len1 = expandAroundCenter(s, i, i);int len2 = expandAroundCenter(s, i, i + 1);int len = Math.max(len1, len2);if (len > end - start) {start = i - (len - 1) / 2;end = i + len / 2;maxLen=Math.max(maxLen, end - start+1);res.add(new int[]{start, end});}}//System.out.println(res.size()); 会把第一个元素的结果添加进去//剔除无效的结果for(int i=0;i<res.size();i++) {int len=res.get(i)[1]-res.get(i)[0]+1;if(len==maxLen)System.out.println(s.substring(res.get(i)[0], res.get(i)[1]+1));}}private static int expandAroundCenter(String s, int left, int right) {int L = left, R = right;while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {L--;R++;}return R - L - 1;}
}