蓝桥杯2015年第六届真题-切开字符串

解题思路:见https://blog.csdn.net/a769973411/article/details/80400792

本人转载并改为java

参考代码:

package dotcpp.字符串;
import java.util.HashSet;
import java.util.Scanner;
public class 切开字符串 {

static int length=100001;
   //判断是否为回文串
  public static boolean echoSubstr(String str)
   {
       for(int i =0;i<str.length()/2;i++)
       {
           if (str.charAt(i)!=str.charAt(str.length()-i-1))
               return false;
       }
       return true;
   }

   public static void main(String[] args) {
       Scanner scanner=new Scanner(System.in);
       int n=scanner.nextInt() ;
       String str,temp =" ";
       str=scanner.next();
       int[] echo =new int[length];//用于存储正回文子串的个数
       int []notEcho=new int[length];//用于存储非正回文子串的个数
       HashSet<String> e=new HashSet<>();
       HashSet<String> ne=new HashSet<>();
       //求正回文的个数
       for (int i =0; i<n;i++)
       {
           for(int j=i;j>=0;j-=2)//注意这里为j-=2
           {
               int t= i-j+1;
               temp=str.substring(j,j+t);
               //判断是否是正回文子串，若是则插入集合，
               //最后通过获取集合的size就可知去掉重复后的非正回文子串个数
               boolean flag =echoSubstr(temp);
               if(flag)e.add(temp);
           }
           echo[i]=e.size();
       }
       //求非正文子串
       for (int i=n-1;i>=0;i--)
       {
           for(int j=i;j<n;j++)
           {
               //判断是否是正回文子串
               boolean flag=false;
               int t=j-i+1;
               temp=str.substring(i,t+i);
               //计算非正回文要先判断它是否是正回文子串
               //因此将子串在正回文子串的集合中找是最节省资源的
               if(temp.length()%2==1)
                   if(e.contains(temp))
                       flag=true;
               if(!flag)ne.add(temp);
           }
           notEcho[i]=ne.size();
       }
       int result=0;
       //求出最大值
       for(int i=1;i<n;i++)
           result=Math.max(result,echo[i-1]*notEcho[i]);
      System.out.println(result);
   }
}