Java最大公共子串（动态规划）

最大公共子串长度问题就是：

求两个串的所有子串中能够匹配上的最大长度是多少。

比如：“abcdkkk” 和 “baabcdadabc”，
可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。

下面的程序是采用矩阵法进行求解的，这对串的规模不大的情况还是比较有效的解法。

请分析该解法的思路，并补全划线部分缺失的代码。

这个有点dp的意思，分别计算两个字符串每一个字符到另一个字符是否相等 若相等 则加前面字符的最大字符串 若前面字符也分别相等则他就等于a[i-1][j-1]+1 若不想等则为0+1

 测试数据1：

  

   

    

     

    
    

     

      abcdkkk
     
    
   

    

     

    
    

     

      baabcdadabc
     
    
  
 

  

   

    

     

    
    

     

      import java.util.Scanner;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      public class Main {
     
    
   

    

     

    
    

     
	static Scanner sc =new Scanner(System.in);
     
    
   

    

     

    
    

     
	
     
    
   

    

     

    
    

     
	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(sc.next(), sc.next());
     
    
   

    

     

    
    

     

      		System.out.println(n);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      }
     
    
  
 

  
 
 

文章来源: laoshifu.blog.csdn.net，作者：红目香薰，版权归原作者所有，如需转载，请联系作者。

原文链接：laoshifu.blog.csdn.net/article/details/117386434