標(biāo)題：切開字符串

Pear有一個字符串，不過他希望把它切成兩段。
這是一個長度為N（<=10^5）的字符串。
Pear希望選擇一個位置，把字符串不重復(fù)不遺漏地切成兩段，長度分別是t和N-t（這兩段都必須非空）。
Pear用如下方式評估切割的方案：
定義“正回文子串”為：長度為奇數(shù)的回文子串。
設(shè)切成的兩段字符串中，前一段中有A個不相同的正回文子串，后一段中有B個不相同的非正回文子串，則該方案的得分為A*B。

注意，后一段中的B表示的是：“...非正回文...”，而不是: “...正回文...”。
那么所有的切割方案中，A*B的最大值是多少呢？

【輸入數(shù)據(jù)】
輸入第一行一個正整數(shù)N（<=10^5）
接下來一行一個字符串，長度為N。該字符串僅包含小寫英文字母。
【輸出數(shù)據(jù)】
一行一個正整數(shù)，表示所求的A*B的最大值。
【樣例輸入】
10
bbaaabcaba
【樣例輸出】
38
【數(shù)據(jù)范圍】
對于20%的數(shù)據(jù)，N<=100
對于40%的數(shù)據(jù)，N<=1000
對于100%的數(shù)據(jù)，N<=10^5


資源約定：
峰值內(nèi)存消耗（含虛擬機(jī)） < 512M
CPU消耗? < 2000ms
請嚴(yán)格按要求輸出，不要畫蛇添足地打印類似：“請您輸入...” 的多余內(nèi)容。
所有代碼放在同一個源文件中，調(diào)試通過后，拷貝提交該源碼。
注意：不要使用package語句。不要使用jdk1.7及以上版本的特性。

注意：主類的名字必須是：Main，否則按無效代碼處理。

思路：藍(lán)橋杯有不少涉及字符串拆分的題目，思路都很清晰，但是實(shí)現(xiàn)起來也會有不少細(xì)節(jié)需要注意，這個題目雖然一開始不太能理解題意，但是我們至少知道需要求判斷回文串這可就是下面代碼中的huiwen()（當(dāng)然題目中進(jìn)一步要求了是長度為奇數(shù)的回文串），對于一個字符串來說，它的回文子串是很多的，所以我們還需要進(jìn)行循環(huán)處理，這就是下面代碼中的panduan()。另一方面，對于B的要求又有不同，我們很難求解出來非正回文串的個數(shù)，但是我們可以求出一個字符串全部的子串個數(shù)，這里對應(yīng)quan()，再減去正回文串的個數(shù)，即可得到B。

完整代碼如下：

import java.util.HashSet; import java.util.Scanner; import java.util.Set;public class Main {static int n;static String str = new String();static int max = 0;static int A, B, C;public static void main(String[] args) {Scanner in = new Scanner(System.in);n = in.nextInt();str = in.next();for (int t = 1; t < n-1; t++) {A = panduan(str.substring(0, t));B = quan(str.substring(t, n)) - panduan(str.substring(t, n));if (max < A*B) {max = A*B;}}System.out.println(max);}/*** B的要求是找出 不相同的非正回文子串 這里采用曲線救國的方案，求出B的 全部不相同子串 的個數(shù)，減去B中 不相同的正回文子串 的個數(shù)* * */private static int quan(String sub) {// TODO Auto-generated method stubSet<String> set = new HashSet<String>();for (int i = 1; i <= sub.length(); i++) {for (int start = 0; start <= sub.length()-i; start++) {String s = sub.substring(start, start+i);set.add(s);}}return set.size();}/*** 對于一個字符串，查找其中包含的正回文串個數(shù)* */private static int panduan(String sub) {// TODO Auto-generated method stubSet<String> set = new HashSet<String>();set.clear();for (int i = 1; i <= sub.length(); i+=2) {for (int start = 0; start <= sub.length()-i; start++) {String s = sub.substring(start, start+i);if (huiwen(s) == true) {set.add(s);}}}return set.size();}/*** 判斷回文* */private static boolean huiwen(String s) {// TODO Auto-generated method stubfor (int i = 0; i < s.length()/2; i++) {if (s.charAt(i) == s.charAt(s.length()-1-i)) {continue;} else {return false;}}return true;} }

總結(jié)

以上是生活随笔為你收集整理的蓝桥杯第六届国赛JAVA真题----切开字符串的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。