动态规划（带图）——查找两个字符串a,b中的最长公共子串_求两个字符串的最长公共子串时间复杂度

查找两个字符串a,b中的最长公共子串

题目

查找两个字符串str1,str2中的最长公共子串。若有多个，输出在较短串中最先出现的那个。

测试用例：

a b c d e f g h i j k l m n o p
a b c s a f j k l m n o p q r s t u v w

动态规划解法：

时间复杂度：O(n^m)
空间复杂度：O(n^2)

    public static String findMaxSubString(String str1,String str2) {
    	//最长字串开始位置
        int begin = 0;
        //长度
        int max = 0;
 		//因为要求是返回短串中较长的字串 所以我们这里默认str1是短串
        if(str1.length() > str2.length()) {
            String tmp = str1;
            str1 = str2;
            str2 = tmp;
        }
        int[][] dp = new int[str1.length()+1][str2.length()+1];
        //不用初始化  默认是 0
        // i 代表短字符串  j 代表长的字符串代表
        //dp[i][i] 中存放的内容代表的是当前有几个字符相等
        for(int i = 1;i < str1.length()+1;i++) {
            for(int j = 1;j < str2.length()+1;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) {     
                    begin = i;//记录字符串最长的末尾下标
                    max = dp[i][j];//记录字符串的长度
                }
            }
        }
        //打印dp数组
        for(int i = 0;i < str1.length();i++) {
            for (int j = 0; j < str2.length(); j++) {
                System.out.print(dp[i][j]+" ");
            }
            System.out.println();
        }
        return str1.substring(begin-max,begin);//begin-max代表的是起始下标
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

对比下dp数组

正是我们想要的！

暴力查找

时间复杂度：0(n^2)
空间复杂度：0(1)

    public static String findMaxSubString1(String s1,String s2) {
    	//记录当前字串长度的
        int maxLen = 0;
        //保存当前字串的值
        String result = "";
        if(s1.length() > s2.length()) {
            String tmp = s1;
            s1 = s2;
            s2 = tmp;
        }
        for (int i = 0; i < s1.length(); i++) {
        	//注意 j <= s1.length();因为substring() 方法是左闭右开的
        	//牛客不取 = 也能过，但是你用它给题目的测试用例是过不了的，少了一个p
            for (int j = i+1; j <= s1.length(); j++) {
                if (s2.contains(s1.substring(i,j)) && s1.substring(i,j).length() > maxLen) {
                    result = s1.substring(i,j);
                    maxLen = s1.substring(i,j).length();
                }
            }
        }
        return result;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

端午节快乐啊！！！