Longest Common Substring Program in Javascript
Given two strings ‘X’ and ‘Y’, find the length of the longest common substring.
Input : X = “GeeksforGeeks”, y = “GeeksQuiz”
Output : 5
The longest common substring is “Geeks” and is of length 5.
We are going to resolve this using dynamic programming.
function lcs(x, y) {
let m = x.length
let n = y.length;
let result = 0;
let dp = {}
for (let i = 0; i <= m; i++) {
dp[i] = [];
}
for (let i = 0; i <= m; i++) {
for (let j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
}
else if (x[i - 1] == y[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
result = Math.max(result, dp[i][j]);
} else {
dp[i][j] = 0
}
}
}
console.log(dp);
return result;
}
let x = "GeeksforGeeks";
let y = "Geeks";
console.log(`Ans is ${lcs(x, y)}`)
Time Complexity: O(m*n)
The only difference in Longest Common Subsequence https://nodeblogger.com/longest-common-subsequence-program-in-javascript/ and Longest Common Substring is that we store Max result when there is a match in string characters and we store 0 if there is no matching of characters.
