Given two strings. The task is to find the length of the longest common substring.
Time : O(nm)
Space : O(min(n,m))
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
classSolution { public:
intlongestCommonSubstr(string a, string b, int n, int m){ if(n < m) returnlongestCommonSubstr(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); }