最长回文子串_

Java

fulai

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;
    }
}

发表于 2025-02-06 13:11:00 回复(0)

Java

Sen_n

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

发表于 2025-01-28 19:51:46 回复(0)

Java

牛客45322975号

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);
            }
        }
    }
}

发表于 2024-10-29 17:20:35 回复(0)

Java

牛客141288675号

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);
    }
}

发表于 2024-07-24 18:40:21 回复(0)

Java

代码边界

双指针中心扩散法

import java.util.*;

public class Main {
    private static int m;
    private static int n;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String line = in.nextLine();
            char[] chars = line.toCharArray();
            int maxLength = 1;
            int left = 0, right = 0;
            int n = 0;
            while (right < chars.length) {
                int length = right - left - 1;
                int start = left, end = right;
                while (start >= 0 && end < chars.length && chars[start] == chars[end]) {
                    start--;
                    end++;
                    length += 2;
                }
                maxLength = Math.max(maxLength, length);
                if (n % 2 == 0) {
                    right++;
                }else {
                    left++;
                }
                n++;
            }
            System.out.println(maxLength);
        }
    }
}

动态规划有两种解法

一种是直接解，dp数组的两个维度分别是子串起点和终点，状态转移公式是：dp[i][j]=dp[i+1][j-1]+2;

另一种就是将先将字符串翻转，题目转化为原字符串和翻转后的字符串最长公共连续子串，这题目就是经典题了，想必大家学dp时都有做过。

发表于 2024-07-03 12:39:36 回复(0)

Java

牛客106397800号

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);
    }
}

发表于 2023-08-13 15:58:56 回复(0)

Java

琥珀川_

和HJ32 密码截取一模一样，直接粘过来

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));

    }
}

发表于 2023-06-30 21:09:23 回复(1)

Java

缘远

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

String str=in.nextLine();

int len=str.length();

if(len<1||len>350)

return;

int count1=0,count2=0;

int pos1=0,pos2=1;

for(int i=1;i<len-1;i++)

{

pos2=i;pos1=i-1;

if(str.charAt(i-1)==str.charAt((i)))

{

pos1=i-1;pos2=i;

}

else if(str.charAt(i-1)==str.charAt((i+1)))

{

pos1=i-1;pos2=i+1;

}

while(str.charAt(pos1)==str.charAt(pos2))

{

count2=pos2-pos1+1;

pos1--;pos2++;

if(pos1<0||pos2>=len)

break;

}

if(count2>count1)

count1=count2;

count2=0;

}

System.out.println(count1);

}

//瞎写

发表于 2023-06-28 22:45:51 回复(0)

Java

SUMMERENT

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;
    }
 }

发表于 2023-06-07 14:30:46 回复(0)

Java

自信的椰子在干饭

回文长度

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);
    }
}

发表于 2023-05-14 18:29:39 回复(0)

Java

牛客604637229号

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

while (in.hasNext()) { // 注意 while 处理多个 case

String a = in.next();

TreeMap<Integer,String> treeMap = new TreeMap<Integer,String>();

for(int i=0;i<a.length();i++){

for(int j=a.length();j>i;j--){

StringBuffer bf = new StringBuffer();

String substr = a.substring(i,j);

bf.append(substr);

String reverse = bf.reverse().toString();

if(substr.endsWith(reverse)){

treeMap.put(substr.length(),substr);

}

System.out.println(treeMap.lastEntry().getKey());

}

发表于 2023-04-19 19:30:23 回复(0)

Java

初之夏

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);
        }
    }
}

发表于 2023-04-09 20:10:54 回复(0)

Java

不想上班悲伤蛙不放弃

/**
 * ☆☆☆☆☆
 * 最长回文子串
 * 中心扩展 + 动态规划 + 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;
            }
        }
    }
}

发表于 2023-03-25 20:07:06 回复(0)

Java

swaggyWW

动态规划

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.hasNext()) { // 注意 while 处理多个 case
            String str = in.nextLine();
            // dp[i][j]数组， 标记下标i-j是否为回文串，
            // 1. 单个字符肯定是回文串， dp[i][i] == true
            // 2. 如果i～j是回文子串，那么i+1～j-1肯定也是回文子串
            String subStr = getMaxLongStr(str);
            System.out.println(subStr.length());
        }
    }

    private static String getMaxLongStr(String str) {
        int begin = 0;
        int maxLen = 1;
        int len = str.length();
        char[] arr = str.toCharArray();
        // 定义dp数组
        // 单个字符都是回文
        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        // dp[i][j] 参考的是 dp[i+1][j-1] 
        // 边界条件： (j-1) - (i+1) + 1 < 2,则不需要参考
        // 整理： j - i < 3
        for (int j = 1; j < len; j++) {
            for (int i = 0; i < j; i ++) {
                if (arr[i] != arr[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                // 更新最大子串
                if (dp[i][j] && j - i + 1 > maxLen) {
                    begin = i;
                    maxLen = j - i + 1;
                }
            }
        }

        return str.substring(begin, begin+maxLen);
    }
}

发表于 2023-03-16 13:53:09 回复(0)

Java

牛客268032525号

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;
    }
}

发表于 2023-03-02 13:26:50 回复(0)

Java

在攒经验的黑眼圈很冷艳

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

// 注意 hasNext 和 hasNextLine 的区别

//中心扩散法，

String str=in.nextLine();

int sum=0;

for(int i=0;i<str.length();i++){

//两种类型的串 ABA。ABBA

int num=GetCount(str,i,i);//奇数串

int num2=GetCount(str,i,i+1);//偶数串

int max=Math.max(num,num2);

if(sum<max) sum=max;

}

System.out.print(sum);

}

//中心扩散法，比较l和r位置的字符是否相同，相同则

private static int GetCount(String str,int l,int r) {

int count=0;

while(l>=0&&r<str.length()&&str.charAt(l)==str.charAt(r)){

l--;

r++;

count=r-l-1;

}

return count;

}

发表于 2023-02-03 16:19:29 回复(0)

Java

洒脱的托尼等oc

想到了一个复杂点但效率高的写法：

就遍历字符串每个字符，然后从这开始通过判断这个字符左右是否对称，对称则说明是回文字符串，且是最短的回文字符串。

如果对称则左右分别向外扩1，再比较两个扩出去的字符。

不同说明左右单个字符不一样，此时就不是回文字符串了，相同则重复。

（注意边界情况）

分两种情况：一种是"aa"。一种是“aba”;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        char[] ch = str.toCharArray();
        int lengthMax = 0;
        for (int i = 0; i < str.length() - 1; i++) {
            // 找到一个长度为2的回文子串
            if (ch[i] == ch[i + 1]) {
                int temp = 1;
                // 该次遍历最长回文串
                String strMax;
                // 同时向该回文子串两边向外递增直至不对称
                while ((i - temp) >= 0 && (i + 1 + temp) < ch.length) {
                    if (ch[i - temp] == ch[i + 1 + temp]) {
                        temp++;
                    } else {
                        break;
                    }
                }
                // 截取temp-1时的情况，此时即当前i时最大回文字符串
                strMax = str.substring(i - temp + 1, i + 1 + temp);
                if (lengthMax < strMax.length()) {
                    lengthMax = strMax.length();
                }
            }

            // 找到一个长度为3的回文子串
            if (i - 1 >= 0 && ch[i - 1] == ch[i + 1]) {
                int temp = 1;
                // 该次遍历最长回文串
                String strMax;
                // 同时向该回文子串两边向外递增直至不对称
                while ((i - 1 - temp) >= 0 && (i + 1 + temp) < ch.length) {
                    if (ch[i - 1 - temp] == ch[i + 1 + temp]) {
                        temp++;
                    } else {
                        // 外扩后左右字符不同时
                        break;
                    }
                }
                // 截取temp-1时的情况，此时即当前i时最大回文字符串
                strMax = str.substring(i - 1 - temp + 1, i + 1 + temp);
                // 找所有最大情况
                if (lengthMax < strMax.length()) {
                    lengthMax = strMax.length();
                }
            }
        }
        System.out.println(lengthMax);
    }
}

发表于 2022-09-20 14:07:03 回复(0)

Java

博客i

求出所有的子字符串，再利用子字符串比较，简单易懂

import java.io.BufferedReader;
import java.io.IOException;
import java.util.*;
import java.util.ArrayList;


public class Main {
    public static void main(String[] args) throws IOException {

        Scanner scan = new Scanner(System.in);
        String str = scan.next();
        if(str.length()==0){
            System.out.print(0);
            return;
        }

        StringBuilder   stb = new StringBuilder(str);
        String temp = stb.reverse().toString();
        int max = 1;
        int len = str.length();
        ArrayList <String> arr = new ArrayList<String>();
        for(int i=0;i<len-1;i++){
            for(int j=i;j<=len;j++){
                arr.add(str.substring(i,j));
            }
        }
        for(int i=0;i<arr.size();i++){
            String ss =arr.get(i);
            if(ss.equals(new StringBuilder(ss).reverse().toString())){
                if(max< ss.length())
                    max = ss.length();
            }


        }
        System.out.print(max);


    }
}

发表于 2022-08-29 16:51:14 回复(2)

最长回文子串

输入描述:

输出描述:

输入

输出

说明

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题