给定一个字符串,求这个字符串的最大回文数.doc
题目：回文判断是一类典型的问题，尤其是与字符串结合后呈现出多姿多彩，在实际应用中比较广泛，下面介绍几个回文的问题。首先我们要介绍一个什么叫回文数：回文，就是指一个字符串顺着读和反着读都是一样的字符串，例如madam，你我你，我爱我 等等一些列的字符串1、首先来判断一下一个字符串是否是回文字符串：java view plaincopyprint?1 public int palindromeNumber(String s, int low, int high) 2 if (low = high) 3 return 1; 4 else if (low < high) 5 if (s.charAt(low) = s.charAt(high) && (high - low) = 1) /防止出现abba等情况 6 return 1; 7 if (s.charAt(low) = s.charAt(high) && (high - low) != 1) /这是类似aba的情况 8 return palindromeNumber(s, low + 1, high - 1); 9 else 10 return 0; 11 else 12 return 0; 13 上面的这个方法，如果输入的字符串是回文字符串的话，则输出1，如果不是的话，输出0，2、已经明白了如何判断一个字符串是否是回文数，接下来我们就要求出一个给定字符串中最大的回文数是多少，就是把这个回文数的长度打出来java view plaincopyprint?14 package programmer; 15 16 import java.util.Scanner; 17 18 /* 19 * 回文判断是一类典型的问题，尤其是与字符串结合后呈现出多姿多彩，在实际中使用也 20 * 比较广泛，而且也是面试题中的常客，所以本文就结合几个典型的例子来体味下回文之趣。 21 * 回文，英文palindrome，指一个顺着读和反过来读都一样的字符串，比如 madam、 22 * 我爱我，这样的短句在智力性、趣味性和艺术性上都颇有特色，中国历史上还有很多 23 * 有趣的回文诗呢 24 */ 25 public class PalindromeNumber 26 27 public int palindromeNumber(String s, int low, int high) 28 if (low = high) 29 return 1; 30 else if (low < high) 31 if (s.charAt(low) = s.charAt(high) && (high - low) = 1) 32 return 1; 33 if (s.charAt(low) = s.charAt(high) && (high - low) != 1) 34 return palindromeNumber(s, low + 1, high - 1); 35 else 36 return 0; 37 else 38 return 0; 39 40 41 /* 42 * 这里求一个字符串中的最长回文字符串的长度，我们使用了枚举的方法，但是这 种方法的时间复杂度还是很大的，浪费了很多不必要的时间和判断，比如当判断 43 * 子串 不是回文时， 就不必要再判断包含本子串的父串了 44 */ 45 public int maxPalindrome1(String s) 46 int len = 0, max = 0; 47 for (int i = 0; i < s.length(); i+) 48 for (int j = s.length() - 1; j >= i; j-) 49 if (palindromeNumber(s, i, j) = 1) 50 len = j - i + 1; 51 52 if (max < len) 53 max = len; 54 55 56 return max; 57 58 59 public static void main(String args) 60 Scanner sc = new Scanner(System.in); 61 String s = sc.nextLine(); 62 System.out.println(new PalindromeNumber().palindromeNumber(s, 0, 63 s.length() - 1); 64 System.out.println(new PalindromeNumber().maxPalindrome1(s); 65 66 上面的思想也十分简单，就是逐个遍历，显然这是十分耗费时间的，时间复杂度为O(n*n*n)，因为还要判断这个是否是回文数，所以比较浪费时间。接下来我们提供一种比较有建设性的方法。3、我们知道回文数是正着读和反着读是一样的，就是说对于一个给定的字符串，如果我们将这个字符串逆置的话，我们就会发现两个字符串有一个最长的连续相同的子序列，则这个连续的最长的共同子序列就是我们要求的回文数，例如：abcabcba，反过来就是abcbacba，显然我们发现两个字符串连续的最长的共同子序列就是abcba，而abcba就是我们索要求的最长的回文数。下面是这个源代码：java view plaincopyprint?67 package programmer; 68 69 import java.util.Scanner; 70 71 public class PalindromeNumber1 72 StringContain obj = new StringContain(); 73 74 public int Max(String s1, String s2) 75 int max = 0; 76 for (int i = 0; i < s1.length(); i+) 77 for (int j = s2.length(); j > i; j-) 78 if (obj.stringContain(s1, s2.substring(i, j) = 1) 79 if (max < j - i) 80 max = j - i; 81 82 83 84 return max; 85 86 87 public String reverseString(String s) 88 char c = new chars.length(); 89 c = s.toCharArray(); 90 for (int i = 0, j = c.length - 1; i < j; i+, j-) 91 char ch = ci; 92 ci = cj; 93 cj = ch; 94 95 return String.valueOf(c); 96 97 98 public static void main(String args) 99 Scanner sc = new Scanner(System.in); 100 String s1 = sc.nextLine(); 101 / System.out.println(s1.subSequence(0, s1.length() - 1); 102 String s2 = new PalindromeNumber1().reverseString(s1); 103 System.out.println(s2); 104 System.out.println(new PalindromeNumber1().Max(s1, s2); 105 106 而其中我们用到了stringContain()方法，这是我写的判断一个字符串是否包含另外一个字符串的算法，代码如下：java view plaincopyprint?107 package programmer; 108 109 import java.util.Scanner; 110 111 /* 112 * 这是判断字符串s1中是否包含字符串s2 113 */ 114 115 public class StringContain 116 public int stringContain(String s1, String s2) 117 int i, j; 118 for (i = 0, j = 0; i < s1.length() && j < s2.length();) 119 if (s1.charAt(i) != s2.charAt(j) 120 if (j != 0) 121 j = 0; 122 else 123 i+; 124 else 125 i+; 126 j+; 127 128 129 if (j = s2.length() 130 return 1; 131 return 0; 132 133 134 public static void main(String args) 135 Scanner sc = new Scanner(System.in); 136 String s1 = sc.nextLine(); 137 String s2 = sc.nextLine(); 138 System.out.println(new StringContain().stringContain(s1, s2); 139 140 可能有些同学要说了，java里面直接就有contains方法，为什么要自己写了？我希望大家在学习算法的时间，最好不用或者少用java的特殊机制，你了解即可，因为算法是考察你的思维敏捷性的，语言的便利并不能给你带来太多思考上的便利。4、难道大家不觉得上面求字符串最长回文数的方法不太好吗，一定有可以优化的地方，实际上也确实是这样的，上面求回文数的方法可以优化的地方在这儿，例如我们要求的字符串还是 abcabcba，上面的几种求法差不多都是这样的思想：将此字符串的所有子字符串列出来，然后判断它们是不是回文数，其实我们不一定非要这样列出字符串，我们知道回文数是对称的，则分为奇数个和偶数个来讨论，现在我们就假设是奇数个，则以中间的那个元素为中心，向两边扩展，再分别判断对称两边的字符是否相等，直到不等为止，然后求出最大的回文数的大小。下面将步骤一一列出如下：以abcabcba为例，i代表中心字符所在的位置(1)i=0，就是从字符a开始，a是起始字符，不好向左边扩展，则继续下去(2)i=1，就是字符b，其左右字符分别为a c，但是 a不等于c，则还要继续下去。下面贴出自己的源代码：java view plaincopyprint?141 public int maxPalindrome2(String s) 142 int len = s.length(); 143 int max = 0; 144 for (int i = 0; i < len; i+) 145 for (int j = 0; (i - j) >= 0 && (i + j) < len; j+) /这是考虑中心元素是奇数个的情况，例如abcba 146 if (s.charAt(i - j) != s.charAt(i + j) 147 break; 148 else 149 max = (max > (2 * j + 1) ? max : (2 * j + 1); 150 151 for (int j = 0; (i - j) >= 0 && (i + j + 1) < len; j+) /这是考虑中心元素个偶数个的情况，例如abccba 152 if (s.charAt(i - j) != s.charAt(i + j + 1) 153 break; 154 else 155 max = (max > (2 * j + 2) ? max : (2 * j + 2); 156 157 158 return max; 159
