首页 > 试题广场 >

HDU 3068 最长回文

[编程题]HDU 3068 最长回文

热度指数：1677 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.
回文就是正反读都是一样的字符串,如aba, abba等

输入描述:

输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S 
两组case之间由空行隔开(该空行不用处理)
       
字符串长度len <= 110000

输出描述:

每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.

示例1

输入

aaaa

abab

输出

4
3

算法知识视频讲解

查看答案及解析

简单易懂的动态规划法

思路：

要找出最长的对称子串，也就是最长回文串。想一下回文串的特点，即 从前往后和从后往前的顺序是一样的，但是其他的干扰字符串可就没这个特点了。所以就想出了一种办法：将原字符串s1逆序得到新的字符串s2，然后找出两个字符串中相同的部分，这个相同的部分就是回文串，然后再考虑一下找出最长的回文串酒好了，题目就转变为求两个字符串的最长公共子串问题。

动态规划解法：

dp含义：

两个字符串对比的情况，一般最简单的dp就是二维的，因此dp[i][j]的含义可以定义为字符串s1的前i个字符和s2前j个字符中，以第i个字符和第j个字符结尾的最长的相同序列长度。

状态转移方程：

对于dp[i][j]来说，如果当前s1中的第i个字符和s2中的第j个字符相同，那么需要考虑s1的前i-1个字符和s2的前j-1个字符，即dp[i][j] = dp[i-1][j-1] + 1；如果不相同，那么就是0。

初始值：

因为涉及到i-1操作，为了防止内存溢出，将dp数组的维度在字符串长度的基础上加1。且元素都初始化为0。

代码：

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
 
using namespace std;
 
string maxHui(string s)
{
    int len = s.length();
    if(len <= 1)
        return s;
    string s2 = s;
    reverse(s2.begin(), s2.end());
    vector<vector<int>> dp(len+1, vector<int>(len+1, 0));
    int res = 0, pos = 0;
    for(int i = 1; i <= len; i++)
    {
        for(int j = 1; j < len+1; j++)
        {
            if(s[i-1] == s2[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            if(res <= dp[i][j])
            {
                res=dp[i][j];
                pos = i-1;
            }
        }
    }
    return s.substr(pos-res+1, res);
}
 
int main()
{
    string str;
    while(getline(cin, str))
        cout << maxHui(str) << endl;
 
    return 0;
}

编辑于 2020-07-23 00:38:33 回复(0)

fengzhk

import java.util.Scanner;
public class Main{
    public static char[] generateArray(String str){
        char[] res = new char[2 * str.length() + 1];
        int index = 0;
        for(int i = 0; i < res.length;i++){
            res[i] = (i & 1) == 0 ? '#':str.charAt(index++);
        }
        return res;
    }
    public static int Manacher(String str){
        char[] charArr = generateArray(str);
        int C = -1;
        int R = -1;
        int max = Integer.MIN_VALUE;
        int[] pArr = new int[charArr.length];
        for(int i = 0 ;i < charArr.length;i++){
            pArr[i] = R > i ? Math.min(R-i,pArr[2 * C - i]) : 1;
            while(i + pArr[i] < pArr.length && i - pArr[i] >= 0){
                if(charArr[i + pArr[i]] == charArr[i - pArr[i]])
                    pArr[i]++;
                else
                    break;
            }
            if(i + pArr[i] > R){
                R = i + pArr[i];
                C = i;
            }
            max = Math.max(max,pArr[i]);
        }
        return max - 1;
    }
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String str = sc.next();
            System.out.println(Manacher(str));
        }
    }
}

发表于 2018-02-26 17:18:36 回复(0)

百度高级测试开发工程师

反正我写了一个在本地可以运行但是这里会有内部错误抱歉我不会处理这里的输入

import java.util.Scanner;

public class Main {
     public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNext()) {
			String string = (String) scanner.next();
			System.out.println(getLongestPalindrome(string, string.length()));
		}
	}
	 public static int getLongestPalindrome(String A, int n) {
         if(A==null)
           return 0;
       char []ch=A.toCharArray();
       int max=0;
       for(int i=0;i<n;i++){
           //先用奇数长度来进行判断
           int len=0;
           for(int j=0;(i-j)>=0&&(i+j)<n;j++){
               if(ch[i-j]!=ch[i+j])
                   break;
               len=2*j+1;
           }
           if(len>max)
               max=len;
           //用偶数长度进行一次判断
            for(int j=0;(i-j)>=0&&(i+j+1)<n;j++){
               if(ch[i-j]!=ch[i+j+1])
                   break;
               len=2*j+2;
           }
           if(len>max)
               max=len;
       }
       return max;

   }


}

发表于 2016-09-03 22:14:54 回复(0)

紫色流星

大家好，请问我的代码提示内部错误，可是在电脑上可以运行是怎么回事？
public class HuiWen {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()){
			String line=sc.nextLine();
			if(line==null)
				return;
			int i=line.length();
//			int max=0;
			while(i>=0){
				if(isPalindrom(line.substring(0, i))){
					System.out.println(i);
					break;
				}else
				i--;
			}
		}
	} 
	public static boolean isPalindrom(String str){
		StringBuffer buf1=new StringBuffer(str);
		StringBuffer buf2=buf1.reverse();
		return buf2.toString().equals(str);
	}
}

发表于 2016-09-05 10:18:50 回复(3)

西红柿炒蛋加糖

import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
String string = sc.nextLine();
if(string.equals("")){
continue;
}
System.out.println(Manacher(string));
}
}

/**
* 马拉车算法的实现
* @param A
* @return
*/
public static int Manacher(String A) {
StringBuffer s = new StringBuffer("#");
for(int i = 0;i < A.length();i++) {
s.append(A.charAt(i));
s.append("#");
}
A = s.toString();
int[] P = new int[A.length()];
int mx = 0, id = 0; //mx代表以id为中心的最长回文的右边界
for(int i = 0;i < A.length();i++) {
if(mx > i)
P[i] = Math.min(P[2 * id - i], mx - i);
else
P[i] = 1;
while(i + P[i] < A.length() && i - P[i] >= 0 && A.charAt(i + P[i]) == A.charAt(i - P[i])) {
P[i]++;
}
//我们每走一步i，都要和mx比较,我们希望mx尽可能的远,这样才能更有机会执行if(mx>i)这句代码，从而提高效率
if(P[i] + i > mx) {
mx = i + P[i];
id = i;
}
}
int result = -1;
int i = 0, t = 0;
for(;i < P.length;i++) {
if(P[i] > result) {
result = P[i];
t = i;
}
}
return result-1;
}
}

发表于 2018-10-09 17:30:51 回复(0)

offer去哪里了

import java.util.Scanner;

/**
 * https://www.nowcoder.com/questionTerminal/edb0f0cc3ffd495bb4826caef5ce9104
 */
public class Main {

    public static char[] manacherString(String str) {
        char[] charArr = str.toCharArray();
        char[] res = new char[str.length() * 2 + 1];
        int index = 0;
        for (int i = 0; i != res.length; i++) {
            res[i] = (i & 1) == 0 ? '#' : charArr[index++];
        }
        return res;
    }

    public static int maxLcpsLength(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        char[] charArr = manacherString(str);
        int[] pArr = new int[charArr.length];
        int index = -1;
        int pR = -1;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i != charArr.length; i++) {
            pArr[i] = pR > i ? Math.min(pArr[2 * index - i], pR - i) : 1;
            while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
                if (charArr[i + pArr[i]] == charArr[i - pArr[i]])
                    pArr[i]++;
                else {
                    break;
                }
            }
            if (i + pArr[i] > pR) {
                pR = i + pArr[i];
                index = i;
            }
            max = Math.max(max, pArr[i]);
        }
        return max - 1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String str = sc.next();
            System.out.println(maxLcpsLength(str));
        }
    }

}

    Manacher算法实现

编辑于 2018-09-09 17:29:11 回复(0)

变红拿offer变红拿offer

java manacher算法超时，我靠

发表于 2017-05-16 15:13:46 回复(1)

嘻嘻里

好难啊

发表于 2017-05-07 18:27:50 回复(0)

爱学习的小蜗牛

超时间了，不知道怎么改
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while (in.hasNext()) {
			String string = in.next();
			if(string==null){
				continue;
			}
			int max = 0;
			for (int i = 0; i < string.length(); i++) {
				String sub;
				for (int j = i + 2; j <= string.length(); j++) {
					sub = string.substring(i, j);
					if (isHuiWen(sub)) {
						if (max < sub.length())
							max = sub.length();
					}
				}
			}
			System.out.println(max);
		}
	}

	public static boolean isHuiWen(String string) {
		boolean flag = true;
		char[] cs = string.toCharArray();
		int n = cs.length;
		for (int i = 0; i < n / 2; i++) {
			if (cs[i] != cs[n - i - 1]) {
				flag = false;
			}
		}
		return flag;
	}
}

编辑于 2017-02-23 12:32:27 回复(0)

颖影风

我自己的代码总是在报内部错误，然后我把你这个通过了的代码贴进去，结果还是内部错误，我搞不懂了。

发表于 2016-09-07 11:25:48 回复(0)

囚牢之徒

内部错误是什么鬼？

发表于 2016-09-06 11:21:37 回复(0)

lizhenfeng

内部错误什么鬼

发表于 2016-08-18 15:43:16 回复(0)

FIA

这题用java输入这块怎么写，谁知道？

发表于 2016-08-03 19:46:50 回复(1)

新世纪的神

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=110005;
char str1[maxn],str2[2*maxn+1];
int pArr[2*maxn+1];
void init(int len){
    int l=len*2+1,j=0;
    for(int i=0;i<l;i++){
        if(i%2==0){
            str2[i]='#';
        }
        else{
            str2[i]=str1[j++];
        }
    }
    str2[l]='\0';
}
int main(){
    //freopen("in.txt","r",stdin);
    int n,m,pR,index,Max;
    while(scanf("%s",str1)==1){
        n=strlen(str1);
        pR=0,index=0,Max=0;
        init(n);
        m=n*2+1;
        for(int i=0;i<m;i++){
            pArr[i]=pR>i?min(pArr[2*index-i],pR-i):1;
            while(i+pArr[i]<m&&i+pArr[i]>-1){
                if(str2[pArr[i]+i]==str2[i-pArr[i]]){
                    pArr[i]++;
                }
                else{
                    break;
                }
            }
            if(pArr[i]+i>pR){
                pR=pArr[i]+i;
                index=i;
            }
            Max=max(Max,pArr[i]);
        }
        printf("%d\n",Max-1);
    }
    return 0;
}

发表于 2016-07-11 10:55:26 回复(0)

提交观点

问题信息

难度：

16条回答 18收藏 5261浏览

通过挑战的用户

查看代码

心文花雨

2019-05-22 23:20:53
入参要判空

2019-05-22 12:59:44
愿D:

2019-05-04 18:42:17
刘禅挥泪斩孔明

2019-04-15 23:36:17
蓝紫坊

2018-10-27 22:39:31