给定一个字符串,求这个字符串的最大回文数

《给定一个字符串,求这个字符串的最大回文数》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、题目：回文判断是一类典型的问题，尤其是与字符串结合后呈现出多姿多彩，在实际应用中比较广泛，下面介绍几个回文的问题。首先我们要介绍一个什么叫回文数：回文，就是指一个字符串顺着读和反着读都是一样的字符串，例如madam，你我你，我爱我等等一些列的字符串1、首先来判断一下一个字符串是否是回文字符串：[java]viewplaincopyprint?1publicintpalindromeNumber(Strings,intlow,inthigh){2if(low==high)3return1;4elseif(low

2、if(s.charAt(low)==s.charAt(high)&&(high-low)==1)//防止出现abba等情况6return1;7if(s.charAt(low)==s.charAt(high)&&(high-low)!=1)//这是类似aba的情况8returnpalindromeNumber(s,low+1,high-1);9else10return0;11}else12return0;13}上面的这个方法，如果输入的字符串是回文字符串的话，则输出1，如果不是的话，输出0，2、已经明白了如何判断一个字符串是否

3、是回文数，接下来我们就要求出一个给定字符串中最大的回文数是多少，就是把这个回文数的长度打出来[java]viewplaincopyprint?14packageprogrammer;1516importjava.util.Scanner;1718/*19*回文判断是一类典型的问题，尤其是与字符串结合后呈现出多姿多彩，在实际中使用也20*比较广泛，而且也是面试题中的常客，所以本文就结合几个典型的例子来体味下回文之趣。21*回文，英文palindrome，指一个顺着读和反过来读都一样的字符串，比如madam、22*我爱我，这样的

4、短句在智力性、趣味性和艺术性上都颇有特色，中国历史上还有很多1*有趣的回文诗呢2*/3publicclassPalindromeNumber{45publicintpalindromeNumber(Strings,intlow,inthigh){6if(low==high)7return1;8elseif(low

5、low)!=1)12returnpalindromeNumber(s,low+1,high-1);13else14return0;15}else16return0;17}1819/*20*这里求一个字符串中的最长回文字符串的长度，我们使用了枚举的方法，但是这种方法的时间复杂度还是很大的，浪费了很多不必要的时间和判断，比如当判断21*子串不是回文时，就不必要再判断包含本子串的父串了22*/23publicintmaxPalindrome1(Strings){24intlen=0,max=0;25for(inti=0;i

6、ength();i++){26for(intj=s.length()-1;j>=i;j--){27if(palindromeNumber(s,i,j)==1){28len=j-i+1;29}30if(max

7、dromeNumber().palindromeNumber(s,0,41s.length()-1));42System.out.println(newPalindromeNumber().maxPalindrome1(s));43}1}上面的思想也十分简单，就是逐个遍历，显然这是十分耗费时间的，时间复杂度为O(n*n*n)，因为还要判断这个是否是回文数，所以比较浪费时间。接下来我们提供一种比较有建设性的方法。3、我们知道回文数是正着读和反着读是一样的，就是说对于一个给定的字符串，如果我们将这个字符串逆置的话，我们就会发现两

8、个字符串有一个最长的连续相同的子序列，则这个连续的最长的共同子序列就是我们要求的回文数，例如：abcabcba，反过来就是abcbacba，显然我们发现两个字符串连续的最长的共同子序列就是abcba，而abcba就是我们索要求的最长的回文数。下面是这个源代码：[java]viewplain