首页 > 试题广场 >

寻找字符串的最长回文

[编程题]寻找字符串的最长回文
  • 热度指数:860 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
输入一个字符串,请找出该字符串的包含的最长回文子字符串
比如,输入babcd,输出bab
输入abbc,输出bb

输入描述:
只包含a-z的的字符串


输出描述:
入参的最长回文子字符串
示例1

输入

babcd

输出

bab
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
usingnamespacestd;
 
intmain(){
    string str="";
    string hui="";
    intbefore=0;
    cin>>str;
    intlen=str.size();
    for(intx=0;x<len;x++){
        intsum1=0,move1=0,f=0;
        while((x-move1>=0)&&(x+move1<len)&&str[x-move1]==str[x+move1]){
            sum1+=2;
            move1++;
            f=1;
        }
        if(f){
            sum1--;
        }
        intsum2=0,move2=0;
        while((x-move2>=0)&&(x+move2+1<len)&&str[x-move2]==str[x+1+move2]){
            sum2+=2;
            move2++;
        }
        if(sum1>sum2){
            if(before<sum1){
                hui=str.substr(x-move1+1,2*move1-1);
                before=sum1;
            }
        }
        else{
            if(before<sum2){
                hui=str.substr(x-move2+1,2*move2);
                before=sum2;
            }
        }
    }
    cout<<hui;
    return0;
}

发表于 2018-12-20 12:37:55 回复(0)
//Manacher算法,参考:https://segmentfault.com/a/1190000008484167
#include<bits/stdc++.h>
usingnamespacestd;
intmain()
{
    string s;
    while(cin >> s)
    {
        string t ="$#";
        for(inti = 0; i < s.size(); i++)
        {
            t += s[i];
            t +="#";
        }
        vector<int> p(t.size());
        p[0] = 0;
        intid = 0, mx = 0, resid = 0, resmx = 0;
        for(inti = 1; i < t.size(); i++)
        {
            p[i] = i < mx ? p[2 * id - i] : 1;
            while(t[i + p[i]] == t[i - p[i]])
                p[i]++;
            if(p[i] + 1>mx)
            {
                mx = p[i] + 1;
                id = i;
            }
            if(p[i] > resmx)
            {
                resmx = p[i];
                resid = i;
            }
        }
        cout << s.substr((resid - resmx) / 2, resmx - 1) << endl;
    }
    system("pause");
    return0;
}

发表于 2018-12-19 13:11:20 回复(0)
//Manacher算法,参考:https://segmentfault.com/a/1190000008484167 #include usingnamespacestd; intmain() {     string s;     while(cin >> s)     {         string t ="$#";         for(inti = 0; i < s.size(); i++)         {             t += s[i];             t +="#";         }         vector p(t.size());         p[0] = 0;         intid = 0, mx = 0, resid = 0, resmx = 0;         for(inti = 1; i < t.size(); i++)         {             p[i] = i < mx ? p[2 * id - i] : 1;             while(t[i + p[i]] == t[i - p[i]])                 p[i]++;             if(p[i] + 1>mx)             {                 mx = p[i] + 1;                 id = i;             }             if(p[i] > resmx)             {                 resmx = p[i];                 resid = i;             }         }         cout << s.substr((resid - resmx) / 2, resmx - 1) << endl;     }     system("pause");     return0; }
发表于 2022-09-24 16:11:05 回复(0)
import java.util.*;

public class Main {
    // 最长回文子串
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        int n = s.length();
        int start = 1, end = 1;
        boolean[][] dp = new boolean[n+1][n+1];
        for (int i = n; i > 0; i--) {
            for (int j = i+1; j <= n; j++) {
                if (s.charAt(i-1) == s.charAt(j-1) && (dp[i+1][j-1] || j - i < 3)) {
                    dp[i][j] = true;
                }
                if (dp[i][j] && j-i > end-start) {
                    end = j;
                    start = i;
                }
            }
        }
        System.out.println(s.substring(start-1, end));
    }
}
发表于 2022-06-29 17:55:12 回复(0)

动态规划方法--改进暴力全子串判断
状态方程:

图片说明 表示字符串s[i:j+1] 出是否为回文子串的判断,T or F

转态转移方程

图片说明
又考虑到,长度为2时的回文子串图片说明 超了范围,所以限定 j-2 > i
最终状态转移方程为:
图片说明

s = input()
n = len(s)
if n <= 1:
    print(s)
else:
    p = [[False for _ in range(n)] for _ in range(n)]
    maxlen = 1
    maxsstr = s[0]
    for r in range(1,n):
        for l in range(r):
            if s[l] == s[r] and (r-l<=2 or p[l+1][r-1]):
                p[l][r] = True
                length = r - l +1
                if length > maxlen:
                    maxlen = length
                    maxsstr = s[l:r+1]
    print(maxsstr)
发表于 2019-09-15 00:45:58 回复(0)
#include <bits/stdc++.h>
using namespace std;
int main()
{
    string str;
    cin >> str;
    int len = str.size();
    int maxLen = 1;
    int start = 0;
    vector<vector<int>> dp(len, vector<int>(len, 0));
    for (int i = 0; i < len; i++) {
        dp[i][i] = 1;
    }
    for (int i = len - 2; i >= 0; i--) {
        for (int j = i + 1; j <len; j++) {
            if (str[i] == str[j]) {
                if (j - i == 1) {
                    dp[i][j] = 2;
                } else {
                    if (dp[i + 1][j - 1] > 0) {
                        dp[i][j] = dp[i + 1][j - 1] + 2;
                    }
                }
            }
            if (maxLen < dp[i][j]) {
                maxLen = dp[i][j];
                start = i;
            }
        }
    }
    cout << str.substr(start, maxLen) << endl;
    return 0;
}

发表于 2019-08-30 16:15:24 回复(0)
import java.util.Scanner;
public class Main {
    private static String res = "";

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        String tmp = "";
        for (int i = 0; i < str.length(); i++) {
            for (int j = i + 1; j <= str.lengt***mp = str.substring(i, j);
                if (isDuichen(tmp)) {
                    if (res.length() < tmp.length()) {
                        res = tmp;
                    }
                }
            }
        }
        System.out.println(res);
    }

    private static boolean isDuichen(String str) {
        String rev = new StringBuffer(str).reverse().toString();
        return rev.equals(str);
    }
}
发表于 2019-03-04 21:23:58 回复(0)
import java.util.*;
public class Main {
    public static int max=-100;
    public static String ss = "";
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        String s = input.nextLine();
            int len = s.length();
            if(len<=1){
                System.out.println(s);
                return;
            }
          for(int i=0;i<len;i++){
              shuangOrDan(s,i,i);//单
              shuangOrDan(s,i,i+1);//双
          }
           System.out.println(ss); 
    }
    public static void shuangOrDan(String str, int start, int end){
        char ch1,ch2;
        while(start>=0&&end<str.length()){
            ch1 = str.charAt(start);
            ch2 = str.charAt(end);
            if(ch1 == ch2){
                if(end+1-start>max){
                    max = end+1-start;
                    ss = str.substring(start,end+1);
                }
                start--;
                end++;
            }
            else
                break;
        }
    }
}
动态规划
发表于 2018-12-19 21:04:47 回复(0)