最长回文子串

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String s = in.nextLine();
            int max = 1;
            for (int i = 1 ; i <= s.length();i++){//子串长度
                for (int j = 0;j <= s.length()-i;j++){//从第几位开始
                    String temp = s.substring(j,j+i);
                    if (isCallBack(temp) && temp.length() > max){
                        max = temp.length();
                    }
                }
            }
            System.out.println(max );
        }
    }
    //判断是否为回子串
    public static boolean isCallBack(String s){
        int length = s.length();
        if ( length == 1){
            return true;
        }
        boolean result = false;
        StringBuilder sb1 = new StringBuilder();
        String s1,s2;
        if (length % 2 == 0){
            s1 = s.substring(0,length/2);
            s2 = s.substring(length/2);
        } else {
            s1 = s.substring(0,length/2);
            s2 = s.substring(length/2 + 1);
        }
        sb1.append(s2);
        String s3 = sb1.reverse().toString();
        if (s3.equals(s1)){
            result = true;
        }
        return result;
    }
}

动态规划，子序列系列经典问题，dp[j][i]含义为:j~i范围内是否为回文子串，初始化dp[i][i]为true,表示单个字符一定是回文的。
初始化res = 1，因为回文子串至少为单个字符，递推公式为两层for循环，外层是右指针，内层是左指针。
右指针从i = 1遍历（因为第一个字符i = 0已经为回文了，所以不需要判断），左指针从j = 0~i（不包含i）遍历，若chars[i] = chars[j],继续判断两者间隔，
若两者间隔小于1，即区间内只有三个字符。直接得出区间内是回文子串，结果res = Math.max(max, i - j + 1)，若区间内不止三个字符，需要继续判断dp[j + 1][i - 1]是否为回文子串，
如果是。dp[j][i] = true，res = Math.max(res, i - j + 1)。遍历结束后返回res即可
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            char[] chars = in.nextLine().toCharArray();
            boolean[][] dp = new boolean[chars.length][chars.length];
            for (int i = 0; i < chars.length; i++){
                dp[i][i] = true;
            }
            int res = 1;
            for (int i = 1; i < chars.length; i++){
                for (int j = 0; j < i; j++){
                    if (chars[i] == chars[j]){
                        if (i - j > 1){
                            if (dp[j + 1][i - 1] == true){
                                dp[j][i] = true;
                                res = Math.max(res, i - j + 1);
                            }
                        }else{
                            dp[j][i] = true;
                            res = Math.max(res, 2);
                        }
                    }
                }
            }
            System.out.println(res);
        }
    }
}

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String s = in.nextLine();
            System.out.println(longestPalindrome(s));
        }
    }

    private static int longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            // 以当前字符为中心扩展（奇数长度）
            int len1 = expand(s, i, i);
            // 以当前字符和下一个字符为中心扩展（偶数长度）
            int len2 = expand(s, i, i+1);
            int longer = Math.max(len1, len2);
            max = Math.max(max, longer);
        }
        return max;
    }

    private static int expand(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

String sb = s.substring(i, i + d);
if (sb.equals(new StringBuilder(sb).reverse().toString())) {  // 回文子串：子串 = 子串反转
    System.out.print(d);
    return;
}

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String str = sc.next();
            ArrayList<Integer> arr = new ArrayList<>();
            if (str.length() % 2 == 0) {
                for (int mid = 1; mid <= str.length() - 2; mid++) {
                    int count = 0;
                    for (int i = 0 ; i < mid ; i++) {
                        if (str.charAt(mid - i - 1) == str.charAt(mid + i)) {
                            count++;
                        } else {
                            break;
                        }
                    }
                    arr.add(count);
                }
                System.out.println(2 * Collections.max(arr));
            }
            if (str.length() % 2 == 1) {
                for (int mid = 1; mid < str.length() - 2; mid++) {
                    int count = 0;
                    for (int i = 0 ; i < mid ; i++) {
                        if (str.charAt(mid - i - 1) == str.charAt(mid + i + 1)) {
                            count++;
                        } else {
                            break;
                        }
                    }
                    arr.add(count);
                }
                System.out.println(2 * Collections.max(arr) + 1);
            }
        }
    }
}

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String string = in.nextLine();

        // 遍历每个字符串
        int maxLen = 0;
        String loopWords = "";
        for(int i = 0; i < string.length(); i++) {
            for(int j = i + 1; j < string.length(); j++) {
                String subString = string.substring(i, j);
                int end = j + subString.length();
                if(end > string.length()) {
                    break;
                }
                String theOtherString = string.substring(j, end);
                String reversedString = new StringBuilder(theOtherString).reverse().toString();
                int loopWordsLen = 2 * subString.length();
                if(subString.equals(reversedString) && loopWordsLen > maxLen) {
                    maxLen = loopWordsLen;
                    loopWords = subString + theOtherString;
                }
            }

            for(int j = 1; j <= i; j++) {
                int left = i - j;
                int right = i + 1 + j;
                if(left < 0 || right > string.length()) {
                    break;
                }

                // abcbaaa
                // i = 2, j = 1:  left = 1 right = 4 ls = 1,2 = b, rs = 3,4 = b
                // i = 2, j = 2:  left = 0 right = 5 ls = 0,2 = ab, rs = 3,5 = ba
                // i = 2, j = 3: break;
                String leftStr = string.substring(left, i);
                String rightStr = string.substring(i + 1, right);
                String reversedRightStr = new StringBuilder(rightStr).reverse().toString();
              
                if(!leftStr.equals(reversedRightStr)) {
                    break;
                }

                int loopWordsLen = 2 * leftStr.length() + 1;
                if(loopWordsLen > maxLen) {
                    maxLen = loopWordsLen;
                    loopWords = leftStr + string.substring(i, i+1) + rightStr;
                }
            }
        }

        System.out.println(maxLen);
    }
}

import java.util.Scanner;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();

        int maxLen = 0;
        for (int i = 0; i < line.length(); i++) {
            for (int j = i + 1; j <= line.length(); j++) {
                // 回文字符串 反转后与其自身相等
                String sub = line.substring(i, j);
                StringBuilder sb = new StringBuilder(sub);
                if (sub.equals(sb.reverse().toString()) && sub.length() > maxLen) {
                    maxLen = sub.length();
                }
            }
        }

        System.out.println(maxLen);
    }
}

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 使用双指针法,从中心点到两边扩散,注意有两种星形式的回文子串
        String str = in.nextLine();
        // 定义左右指针
        int l;
        int r;
        // 定义集合接收回文字符的长度
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < str.length() - 2; i++) {
            // ABBA型
            int len1 = 0;
            if (str.charAt(i) == str.charAt(i + 1)) {
                // 两边发散继续寻找
                l = i;
                r = i + 1;
                do {
                    len1 += 2;
                    l--;
                    r++;
                } while (r < str.length() && str.charAt(l) == str.charAt(r));
            }
            // ABA型 不是加2 初始值是1
            int len2 = 1;
            if (str.charAt(i) == str.charAt(i + 2)) {
                // 两边发散继续寻找
                l = i;
                r = i + 2;
                do {
                    len2 += 2;
                    l--;
                    r++;
                    //防止数组越界异常前置判断
                } while (l >= 0 && r < str.length() && str.charAt(l) == str.charAt(r));
            }
            list.add(Math.max(len1, len2));
        }
        System.out.println(Collections.max(list));

    }
}

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String a = in.nextLine();
        int max = 0;
        for (int i = 0; i < a.length(); i++) {
            for (int j = i+1; j <= a.length(); j++) {
               String sub = a.substring(i,j);
               if (isPalindrome(sub) && sub.length() > max){
                   max = sub.length();
               }
            }
        }
        System.out.println(max);
    }
    private static boolean isPalindrome(String str){
       StringBuilder sub = new StringBuilder(str).reverse();
       if (str.equals(sub.toString())){
           return true;
       }
       return false;
    }
 }   

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String line = in.nextLine();

        int num = 1; // 默认回文最小长度为1(单个字符)
        for (int i = 0; i < line.length(); i++) {
            // 回文长度为偶数
            int k = Math.min(i + 1, line.length() - i - 1);
            int idx = 0;
            while (k > idx) {
                if (line.charAt(i - idx) != line.charAt(i + 1 + idx)) {
                    break;
                }
                idx++;
            }
            num = Math.max(num, 2 * idx);

            // 回文长度为奇数
            k = Math.min(i, line.length() - i - 1);
            idx = 0;
            while (k > idx) {
                if (line.charAt(i - 1 - idx) != line.charAt(i + 1 + idx)) {
                    break;
                }
                idx++;
            }
            num = Math.max(num, 2 * idx + 1);
        }
        System.out.println(num);
    }
}

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static int[] p1=new int[400];
    public static int[] p2=new int[400];
    public static int[] p3=new int[400];
    public static int[] dp=new int[400];
    public static boolean check(int x,int y){
        int a=p2[y]-p2[x-1]*p1[y-x+1];
        int b=p3[x]-p3[y+1]*p1[y-x+1];
        return a==b;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            Arrays.fill(p2,0);
            Arrays.fill(p3,0);
            Arrays.fill(dp,0);
            String s=in.next();
            int n=s.length(),ans=0;
            p1[0]=1;
            for(int i=1;i<=n;i++){
                dp[i]=1;
                p1[i]=p1[i-1]*27;
                p2[i]=p2[i-1]*27+(s.charAt(i-1)-'a');
                p3[n-i+1]=p3[n-i+2]*27+(s.charAt(n-i)-'a');
            }
            for(int i=1;i<=n;i++){
                if(i-dp[i-1]>0&&check(i-dp[i-1],i)) dp[i]=Math.max(dp[i-1]+1,dp[i]);
                if(i-1-dp[i-1]>0&&check(i-1-dp[i-1],i)) dp[i]=Math.max(dp[i-1]+2,dp[i]);
                ans=Math.max(ans,dp[i]);
            }
            System.out.println(ans);
        }
    }
}

/**
 * ☆☆☆☆☆
 * 最长回文子串
 * 中心扩展 + 动态规划 + Manacher
 */
private static void longestPalindrome2() {
    Scanner in = new Scanner(System.in);
    while (in.hasNext()) {
        String s = in.nextLine();
        // 字符间隔及两边插入#，方便统一中心扩展方式的两种情况：中心在元素上和中心在元素间
        StringBuilder sb = new StringBuilder("#");
        for (int i = 0; i < s.length(); i++) {
            sb.append(s.charAt(i)).append("#");
        }
        // 数组用于存插入#后，当前元素为中心的最大回文半径（自身算1）
        // 最终的最大回文长度是该半径-1（该半径多出来的#，比另一边的原字符多一）
        int[] arr = new int[sb.length()];
        // 已知的所有回文串的最右边界+1
        int maxPos = 0;
        // 边界最右的回文串的中心
        int index = 0;
        for (int i = 0; i < sb.length(); i++) {
            if (i < maxPos) {
                // 此处是关键，i相对index的对称位置2*index-i，直接参与计算，避免重复计算
                arr[i] = Math.min(arr[2 * index - i], maxPos - i);
            } else {
                arr[i] = 1;
            }
            // 在已有基础上继续扩展判断，越界判断，以及两边字符判断
            while (i - arr[i] >= 0 && i + arr[i] < sb.length() && sb.charAt(i - arr[i]) == sb.charAt(i + arr[i])) {
                arr[i]++;
            }
            // 更新maxpos和index
            if (i + arr[i] > maxPos) {
                maxPos = i + arr[i];
                index = i;
            }
        }
        int max = 0;
        for (int i = 0; i < sb.length(); i++) {
            max = Math.max(max, arr[i]);
        }
        // 最长回文串的长度
        System.out.println(max - 1);
        // 最长回文串
        for (int i = 0; i < sb.length(); i++) {
            if (max == arr[i]) {
                String result = sb.substring(i - arr[i] + 1, i + arr[i]).replace("#", "");
                System.out.println(result);
                break;
            }
        }
    }
}

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s1 = in.nextLine();
        in.close();

        int size = s1.length();
        int res = 1;
        for (int k = 0; k < size; k++) {
            res = Math.max(res, centreExtend(s1, k, k, size));
        }
        for (int k = 0; k < size-1; k++) {
            if (s1.charAt(k) == s1.charAt(k+1)) {
                res = Math.max(res, centreExtend(s1, k, k+1, size));
            }
        }
        System.out.println(res);
    }

    private static int centreExtend(String s1, int i, int j, int size) {
        while (i-1 >= 0 && j+1 < size && s1.charAt(i-1) == s1.charAt(j+1)) {
            i--;
            j++;
        }
        return j - i + 1;
    }
}