C++ 解法, 执行用时: 3ms, 内存消耗: 420KB, 提交时间: 2022-07-18

class LongestSubstring {
public:
    int findLongest(string A, int n, string B, int m) {
        int len1 = A.size(), len2 = B.size();
        if(len1 == 0 || len2 == 0) return 0;
        maxLen = 0;
        st = -1;
        
        for(int j = len2-1; j >= 0; --j) diag(A, len1, B, len2, 0, j);
        for(int i = 1; i < len1; ++i) diag(A, len1, B, len2, i, 0);
        
        return maxLen;
    }
    
private:
    int maxLen, st;
    
    void diag(string &s1, const int m, string &s2, const int n, int i, int j){
        int curLen = 0;
        while(i < m && j < n){
            if(s1[i] == s2[j]){
                ++curLen;
            }
            else{
                curLen = 0;
            }
            
            if(curLen > maxLen){
                maxLen = curLen;
                st = i - curLen + 1;
            }
            
            ++i;
            ++j;
        }
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 484KB, 提交时间: 2020-09-10

class LongestSubstring {
public:
    int findLongest(string A, int n, string B, int m) {
    vector<int> dp(B.size()+1);
    int tmp=0;
    int ans=0;
    for (int i = 1; i <= A.size(); i++) {
        int last=0; //对角线
        for (int j = 1; j <= B.size(); j++) {
            tmp=dp[j];  //正上方
            if (A[i - 1] == B[j - 1])
                dp[j] = last + 1;
            else
                dp[j]=0;
            last=tmp;
            ans=max(ans,dp[j]);    
        }
    }
    return ans;
    }
};