Longest Common Substring

Given two strings. The task is to find the length of the longest common substring.

• Time : O(nm)
• Space : O(min(n,m))

c++

class Solution {
public:

    int longestCommonSubstr(string a, string b, int n, int m) {
        if(n < m) return longestCommonSubstr(b, a, m, n);
        vector<int> dp(m + 1);
        int res = 0;
        for(int i = 1; i <= n; i++) {
            vector<int> ndp(m + 1);
            for(int j = 1; j <= m; j++) {
                if(a[i-1] == b[j-1]) ndp[j] = dp[j-1] + 1;
                res = max(res, ndp[j]);
            }
            swap(dp, ndp);
        }

        return res;
    }
};