最长公共子串

男娘i 2022-12-07 15:23 184阅读 0赞

# 题目： #

[\[编程题\]最长公共子串][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]

# 题解： #

**对比：[1143. 最长公共子序列][1143.]**

借助一下《图解算法》中的例子。假设对于两个字符串 fish 和 hish，我们可以绘制一个这样的表格，来求解它们最长的公共子串，即：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 1]  
注意，最长公共子串的最终答案并不一定在最后一个格子里，所以我们还需要一个变量 max 来记录最大值。

注意：

如果我们还需要知道具体的最长公共子串是什么，那么就需要再添加一个变量，记录最大值出现的位置，然后往前取最长公共子串的长度即可。

# 代码： #

public class 最长公共子串 { 
    
        public static int findLongest(String A, int n, String B, int m) { 
            // dp[i][j] 表示 S1 的前 i 个字符与 S2 的前 j 个字符最长公共子串的长度。
            int dp[][] = new int[n + 1][m + 1];
            int max = 0;
            for(int i = 1; i <= n; i++)
            { 
                for(int j = 1; j <= m; j++)
                { 
                    // 当 S1.i == S2.j 时，那么就能在 S1 的前 i-1 个字符与 S2 的前 j-1 个字符最长公共子串的基础上再加上 S1.i 这个值，最长公共子串长度加 1.
                    if(A.charAt(i - 1) == B.charAt(j - 1))
                    { 
                        dp[i][j] = dp[i- 1][j - 1] + 1;
                        max = Math.max(max, dp[i][j]);
                    }
                    // 当 S1.i != S2.j 时，此时最长公共子串为0
                    else
                    { 
                        dp[i][j] = 0;
                    }
                }
            }
            // 对于长度为 N 的子串 S1 和长度为 M 的子串 S2，max 就是子串 S1 和子串 S2 的最长公共子串长度。
            return max;
        }
    
        public static void main(String[] args) { 
            String text1 = "1AB2345CD";
            int n = 9;
            String text2 = "12345EF";
            int m = 7;
            int res = findLongest(text1, n, text2, m);
            System.out.println(res);
        }
    
    }

# 参考： #

1.  [动态规划：最长公共子串 & 最长公共子序列][Link 2]
2.  [笔试面试算法经典–最长公共子串（Longest Common SubString）][Longest Common SubString]

[Link 1]: https://www.nowcoder.com/questionTerminal/02e7cc263f8a49e8b1e1dc9c116f7602
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/0af0c09b0d594da0913d6823c55fa486.png
[1143.]: https://zhangyx.blog.csdn.net/article/details/108626165
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/ce15ae94ff7a450387892086c6f72a82.png
[Link 2]: https://blog.csdn.net/afei__/article/details/83153399
[Longest Common SubString]: https://blog.csdn.net/u013309870/article/details/69479488