[Geeks for Geeks] Longest Common Substring

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))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/05/20/PS/GeeksforGeeks/longest-common-substring/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.