最长公共子串

算法知识视频讲解

中等 通过率：27.18% 时间限制：5秒 空间限制：500M

知识点动态规划

• 题目
• 题解(34)
• 讨论(132)
• 排行

描述

给定两个字符串str1和str2,输出两个字符串的最长公共子串

题目保证str1和str2的最长公共子串存在且唯一。

示例1

输入：

"1AB2345CD","12345EF"

复制

返回值：

"2345"

复制

备注：

1 \leq |str_1|, |str_2| \leq 5\,0001≤∣str1∣,∣str2∣≤5000

class Solution {
public:
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    string LCS(string str1, string str2) {
        // write code here
        // 双序列型号dp
        // 定义dp[i][j]代表 s[1:i] t[1:j] 最长的公共子串
        if(str1.empty()||str2.empty()) {
            return 0;
        }
        
        vector<vector<int>> dp(str1.size()+1,vector<int>(str2.size()+1,0));
        
        for(int i=1;i<=str1.size();i++) {
            for(int j=1;j<=str2.size();j++) {
                if(str1[i-1]==str2[j-1]) {
                    if(dp[i-1][j-1]+1>dp[i-1][j]&&dp[i-1][j-1]+1>dp[i][j-1] ) {
                        dp[i][j]=dp[i-1][j-1]+1;
                    } else {
                        dp[i][j] = dp[i-1][j]>dp[i][j-1]? dp[i-1][j] : dp[i][j-1];
                    }
                } else {
                     dp[i][j] =0;
                }
            }
        }
        
        
        int res=0;
        int index=0;
        
        
       for(int i=0;i<dp.size();i++) {
           for(int j=0;j<dp[0].size();j++) {
               if(res<dp[i][j]) {
                   res=dp[i][j];
                   index=j;
               }
           }
       }
       
        return str2.substr(index-res,res);
        
        
    }
};

其实vector里面放string也是可以的，只是内存会不满足题目要求

所以用int来记录一下结尾和个数

所以最后dp[i][j]定义为再s以i结尾 t以j结尾的最长公共子串，所以最后dp[i][j]如果不等的时候dp[i][j]=0