最长公众子串

Question

解析

• dp 矩阵第一列即 dp[0~N-1][0] ，对某一个位置 (i,0) 来说，如果 str1[i] == str2[0] ，令 dp[i][0] = 1 ，否则令 dp[i][0] = 0 ；
• 矩阵 dp 第一行，即 dp[0][0~M-1] ，对某个位置 (0,j) 来说，如果 str1[0] == str2[j] ，令 dp[0][j] = 1 ，否则令 dp[0][j] = 0 ；
• 一般的位置有两种情况，如果 str1[i] != str2[j] ，说明在必须把 str1[i] 和 str2[j] 当做公共子串最后一个字符是不可能的，所以 dp[i][j] = 0 ； 如果 str1[i] = str2[j] ，说明可以将 str1[i] 和 str2[j] 作为公共子串的最后一个字符，其长度就是 dp[i-1][j-1] + 1 ；

import java.util.*;

public class LongestSubstring {
    public int findLongest(String A, int n, String B, int m) {
        char[] sa = A.toCharArray();
        char[] sb = B.toCharArray();
        int[][] dp = new int[sa.length][sb.length];
        for(int i = 0; i < sa.length; i++) //注意和最长公共子序列有点不同
            dp[i][0] = sa[i] == sb[0] ? 1 : 0;
        for(int j = 0; j < sb.length; j++)
            dp[0][j] = sa[0] == sb[j] ? 1 : 0;
        int res = 0;
        for(int i = 1; i < sa.length; i++){
            for(int j = 1; j < sb.length; j++){
                if(sa[i] == sb[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    res = Math.max(res, dp[i][j]);
                }
            }
        }
        return res;  //dp 数组中的最大值，就是最大公共字串的长度
    }
}

由 dp 表生成答案字符串也是不难的，找到最大值，然后往左边的 res 个字符就是答案。

测试程序:

public class LCSub {

    public static int[][] getDp(char[] sa,char[] sb){
        int[][] dp = new int[sa.length][sb.length];
        for(int i = 0; i < sa.length; i++) //注意和最长公共子序列有点不同
            dp[i][0] = sa[i] == sb[0] ? 1 : 0;
        for(int j = 0; j < sb.length; j++)
            dp[0][j] = sa[0] == sb[j] ? 1 : 0;
        int res = 0;
        for(int i = 1; i < sa.length; i++){
            for(int j = 1; j < sb.length; j++){
                if(sa[i] == sb[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    res = Math.max(res, dp[i][j]);
                }
            }
        }
        System.out.println(res);  //4
        return dp;  //dp 数组中的最大值，就是最大公共字串的长度
    }

    /** 根据 dp 表得到答案*/
    public static String getLongestSubstring(String sa, String sb, int[][] dp){
        if(sa == null || sb == null || sa.length() == 0 || sb.length() == 0)
            return "";
        int max = 0, end = 0;
        for(int i = 0; i < dp.length; i++){
            for(int j = 0; j < dp[0].length; j++){
                if(dp[i][j] > max){
                    max = dp[i][j];
                    end = i;
                }
            }
        }
        return sa.substring(end - max + 1, end+1);
    }

    public static void main(String[] args) {
        String sa = "abcdefq";
        String sb = "cdefab";
        int[][] dp = getDp(sa.toCharArray(), sb.toCharArray()); 
        System.out.println(getLongestSubstring(sa, sb, dp)); // cdef
        System.out.println(getLongestSubstring(sa, sb, dp).length()); //4
    }
}

另外，还有一种可以优化空间的做法:

• 因为 dp[i][j] 只依赖于左上角位置的 dp[i-1][j-1] ，所以用一个变量记录左上角的值即可。
• 遍历方向从右上角的斜线开始，一直遍历到左下角，中间记录最大值 max 和结束位置 end 即可。
  

代码如下:

    public static String getLongestSubstring2(String sa,String sb){
        if(sa == null || sb == null || sa.length() == 0 || sb.length() == 0)
            return "";
        char[] chs1 = sa.toCharArray();
        char[] chs2 = sb.toCharArray();
        int row = 0, col = chs2.length-1; //从右上角开始
        int max = 0, end = 0; //记录最大长度和结束位置
        while(row < chs1.length){
            int i = row, j = col;
            int ul = 0;
            while(i < chs1.length && j < chs2.length){ //从(i,j) 向右下方开始遍历
                if(chs1[i] == chs2[j])
                    ul++;
                else
                    ul = 0;
                if(ul > max){ //记录最大值以及结尾字符的位置
                    max = ul;
                    end = i;
                }
                i++;
                j++;
            }
            if(col > 0) // 斜线还没到最左边 -->　往左移动
                col--;
            else
                row++;  //到了最左  --> 往下移动
        }
        System.out.println(max);
        return sa.substring(end-max+1, end+1); // [end-max+1, end]
    }

题目链接

https://www.nowcoder.com/questionTerminal/02e7cc263f8a49e8b1e1dc9c116f7602?toCommentId=1532408