欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

蓝桥杯第八届真题javaB组--06:最大公共子串

程序员文章站 2022-05-11 22:49:39
...

点击查看:蓝桥杯历年真题 题解目录

06. 最大公共子串

蓝桥杯第八届真题javaB组--06:最大公共子串

评测标准答案:a[i-1][j-1]+1
1. 注意区别 最大公共子串(字符连续)和最大公共子序列(字符可以不连续)
2. 手动建立二维字符串匹配表,表内填写已匹配的个数
3. 经过分析 二维表可得到 每次新成功匹配一个字符,都为左上角的数字+1
public class Main{
    static int f(String s1, String s2){
    char[] c1 = s1.toCharArray( );
    char[] c2 = s2.toCharArray( );
    int[][] a = new int[c1.length+1][c2.length+1];
    int max = 0;
    for(int i=1; i<a.length; i++){
         for(int j=1; j<a[i].length; j++){
             if(c1[i-1]==c2[j-1]) {
                 a[i][j] = a[i-1][j-1]+1;  //填空 
                 if(a[i][j] > max)  max = a[i][j];
             }
          }
     }
     return max;
     } 
     public static void main(String[] args){
   	 int n = f("abcdkkk", "baabcdadabc");
  	 System.out.println(n);
     }
}

蓝桥杯第八届真题javaB组--06:最大公共子串