题目主要信息：查找两个字符串str1，str2中的最长的公共子串保证str1和str2的最长公共子串存在且唯一举一反三：学习完本题的思路你可以解决如下题目：BM65 最长公共子序列(二)BM71.最长上升子序列(一)BM73 最长回文子串BM75 编辑距离(一)BM76 正则表达式匹配BM77 最长的括号子串方法一：枚举（前置方法，超时，不能完全通过）思路：最简单直观的方式大概就是枚举了，枚举所有的子串进行比较，但是太复杂了。其实找子串不用一样完全枚举，还可以尝试改良一下具体做法：step 1：我们完全可以遍历两个字符串的所有字符串作为起始step 2：然后同时开始检查字符是否相等，相等则不断后移，增加子串长度，如果不等说明以这两个为起点的子串截止了，不会再有了。step 3：后续比较长度维护最大值即可。图示：Java实现代码：import java.util.*;public class Solution {    public String LCS (String str1, String str2) {        int length = 0;        String res = "";         //遍历s1每个起始点        for(int i = 0; i < str1.length(); i++){             //遍历s2每个起点            for(int j = 0; j < str2.length(); j++){                 int temp = 0;                String temps = "";                int x = i, y = j;                //比较每个起点为始的子串                while(x < str1.length() && y < str2.length() && str1.charAt(x) == str2.charAt(y)){                     temps += str1.charAt(x);                    x++;                    y++;                    temp++;                }                //更新更大的长度子串                if(length < temp){                     length = temp;                    res = temps;                }            }        }        return res;    }}C++实现代码：class Solution {public:    string LCS(string str1, string str2) {        int length = 0;        string res = "";         //遍历s1每个起始点        for(int i = 0; i < str1.length(); i++){             //遍历s2每个起点            for(int j = 0; j < str2.length(); j++){                 int temp = 0;                string temps = "";                int x = i, y = j;                //比较每个起点为始的子串                while(x < str1.length() && y < str2.length() && str1[x] == str2[y]){                     temps += str1[x];                    x++;                    y++;                    temp++;                }                //更新更大的长度子串                if(length < temp){                     length = temp;                    res = temps;                }            }        }        return res;    }};Python代码实现：（Python版本不超时）class Solution:    def LCS(self , str1: str, str2: str) -> str:        #让str1为较长的字符串        if len(str1) < len(str2):             str1, str2 = str2, str1        res = ''        max_len = 0        #遍历str1的长度        for i in range(len(str1)):             #查找是否存在            if str1[i - max_len : i + 1] in str2:                 res = str1[i - max_len : i + 1]                max_len += 1        return res复杂度分析：时间复杂度：O(m2n)O(m^2n)O(m2n)，其中mmm是str1的长度，nnn是str2的长度，分别枚举两个字符串每个字符作为起点，后续检查子串长度最坏需要花费O(m)O(m)O(m)空间复杂度：O(n)O(n)O(n)，res属于返回必要空间，temps属于临时辅助空间，最坏情况下长度为nnn方法二：动态规划（推荐使用）知识点：动态规划动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果思路：动态规划继承自方法一，在枚举的基础上用动态规划来改进。具体做法：step 1：我们可以用dp[i][j]dp[i][j]dp[i][j]表示在str1中以第iii个字符结尾在str2中以第jjj个字符结尾时的公共子串长度，step 2：遍历两个字符串填充dp数组，转移方程为：如果遍历到的该位两个字符相等，则此时长度等于两个前一位长度+1，dp[i][j]=dp[i−1][j−1]+1dp[i][j] = dp[i - 1][j - 1] + 1dp[i][j]=dp[i−1][j−1]+1，如果遍历到该位时两个字符不相等，则置为0，因为这是子串，必须连续相等，断开要重新开始。step 3：每次更新dp[i][j]dp[i][j]dp[i][j]后，我们维护最大值，并更新该子串结束位置。step 4：最后根据最大值结束位置即可截取出子串。Java实现代码：import java.util.*;public class Solution {    public String LCS (String str1, String str2) {        //dp[i][j]表示到str1第i个个到str2第j个为止的公共子串长度        int[][] dp = new int[str1.length() + 1][str2.length() + 1];         int max = 0;        int pos = 0;        for(int i = 1; i <= str1.length(); i++){            for(int j = 1; j <= str2.length(); j++){                //如果该两位相同                if(str1.charAt(i - 1) == str2.charAt(j - 1))                     //则增加长度                    dp[i][j] = dp[i - 1][j - 1] + 1;                 else                     //该位置为0                    dp[i][j] = 0;                 //更新最大长度                if(dp[i][j] > max){                     max = dp[i][j];                    pos = i - 1;                }            }        }        return str1.substring(pos - max + 1, pos + 1);    }}C++实现代码：class Solution {public:    string LCS(string str1, string str2) {        //dp[i][j]表示到str1第i个个到str2第j个为止的公共子串长度        vector<vector<int> > dp(str1.length() + 1, vector<int>(str2.length() + 1, 0));         int max = 0;        int pos = 0;        for(int i = 1; i <= str1.length(); i++){            for(int j = 1; j <= str2.length(); j++){                //如果该两位相同                if(str1[i - 1] == str2[j - 1]){                     //则增加长度                    dp[i][j] = dp[i - 1][j - 1] + 1;                 }                else{                     //该位置为0                    dp[i][j] = 0;                 }                //更新最大长度                if(dp[i][j] > max){                     max = dp[i][j];                    pos = i - 1;                }            }        }        return str1.substr(pos - max + 1, max);    }};Python代码实现：（Python版本超时，不能完全通过）class Solution:    def LCS(self , str1: str, str2: str) -> str:        #dp[i][j]表示到str1第i个个到str2第j个为止的公共子串长度        dp = [[0] * (len(str2) + 1) for i in range(len(str1) + 1)]        max = 0        pos = 0        for i in range(1, len(str1) + 1):            for j in range(1, len(str2) + 1):                #如果该两位相同                if str1[i - 1] == str2[j - 1]:                     #则增加长度                    dp[i][j] = dp[i - 1][j - 1] + 1                 else:                     #该位置为0                    dp[i][j] = 0                 #更新最大长度                if dp[i][j] > max:                     max = dp[i][j]                    pos = i - 1        return str1[pos - max + 1: pos + 1]复杂度分析：时间复杂度：O(mn)O(mn)O(mn)，其中mmm是str1的长度，nnn是str2的长度，遍历两个字符串所有字符空间复杂度：O(mn)O(mn)O(mn)，dp数组大小为m∗nm*nm∗n