输出两个字符串最长公共子串的长度

题目描述

给定两个只包含小写字母的字符串，计算两个字符串的最大公共子串的长度。注：子串的定义指一个字符串删掉其部分前缀和后缀（也可以不删）后形成的字符串。

动态规划方法解题

$dp[i][j]$ 表示以 $str1[i]$ 和 $str2[j]$ 为结尾的最长公共子串的长度状态迁移方程：当 $str1[i]$ == $str2[j]$ 时，$dp[i][j]$ = $dp[i-1][j-1]+1$
否则，$dp[i][j] = 0$最优解为：$max(dp[i][j])$

代码实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Main m = new Main();
        String a ,b;
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
             a = in.nextLine();
             b = in.nextLine();
             int num = m.MaxCommonSub(a,b);
             System.out.print(num);
        }
    }
    
    public static int MaxCommonSub(String a ,String b){
        int maxNum = 0;
        int n = a.length();
        int m = b.length();
        int dp[][] = new int[n+1][m+1];
        char c1,c2;
        for(int i=1;i<=n;i++){
            c1 = a.charAt(i-1);
            for(int j=1;j<=m;j++){
                c2 = b.charAt(j-1);
                    if(c1 == c2){
                        dp[i][j] = dp[i-1][j-1]+1;
                    }else{
                        dp[i][j] =0;
                    }
                maxNum = Math.max(maxNum,dp[i][j]);
            }
        }
    return maxNum;
    }
}

原题链接 华为机试：公共子串计算长度