求两个字符串的最长公共子串

2023-12-26 23:41:41

视频讲解:
https://www.bilibili.com/video/BV1hv41117gC/?spm_id_from=333.788.recommend_more_video.0&vd_source=0b928a12dede193d54766685a9e5a932

import java.util.Arrays;
import java.util.Scanner;

public class SelectRepeatCode {

    public static void main(String [] args){
        Scanner sc = new Scanner(System.in);

        String str1 = sc.nextLine();
        String str2 = sc.nextLine();

        System.out.println(getResult(str1,str2));
    }
    public static String getResult(String str1,String str2){
        int n = str1.length();
        int m = str2.length();

        int[][] dp = new int[n+1][m+1];

        int max = 0;
        String ans = "";

        for (int i = 1; i<= n; i++){
            for (int j = 1; j<=m; j++){
                if (str1.charAt(i-1) == str2.charAt(j-1)){
                    //dp[i-1][j-1]代表前面的字符串(长度)
                    dp[i][j] = dp[i-1][j-1] + 1;    

                    if (dp[i][j] > max){
                        max = dp[i][j];
                        ans = str1.substring(i - max,i);
                    }
                }
                else{
                    dp[i][j] = 0;
                }
            }
        }
//        for (int i = 0; i < dp.length; i++){
//            String dps = Arrays.toString(dp[i]);
//            System.out.println(dps);
//        }

        return ans;
    }
}

文章来源:https://blog.csdn.net/qq_38327117/article/details/135233243
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。