最长公共子串

题目

已知有两个字符串s1,s2，求其最长公共子串。

思路

定义dp[i][j]表示s1[0,i],s2[0,j]最长公共子串的长度，则dp[i][j]=dp[i-1][j-1]+1,s1[i]==s2[j]
,dp[i][j]=0,s1[i]!=s2[j]。dps1.length-1就是答案的最长长度

代码

#include <vector>
using namespace std;
class CommonString {
public:
    string longestCommonString(string s1, string s2) {
        int n = s1.length();
        int m = s2.length();
        vector<vector<int>> dp(n,vector<int>(m));
        int location = 0;
        int longest = 0;
        for(int i = 0;i < n;i++) {
            for(int j = 0;j < m;j++) {
                if (s1[i] == s2[j]) {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    }
                    else {
                        dp[i][j] = dp[i-1][j-1]+1;
                    }
                    
                    if (dp[i][j] > longest) {
                        longest = dp[i][j];
                        location = i;
                    }
                }
                else {
                    dp[i][j] = 0;
                }
            }
        }
        return longest == 0 ? "":s1.substr(location-longest+1,longest);
    }
};