In this article, we will see how to find the longest common substring between two strings in JavaScript.
A substring is a contiguous sequence of characters within a string. It can be obtained by extracting part of the string starting from any position. We are going to write a JavaScript function that will take two strings and find the common longest consecutive string.
There are two approaches to finding the longest common substring between two strings
- Brute-force approach
- Dynamic programming
Approach 1: Brute-force approach
In this method, we create all possible substrings from both strings and compare them to determine which substring has the longest length in common. The findLongestCommonSubstring() function uses nested loops to generate all possible substrings and compares them to find the longest common substring. In this example, the function findLongestCommonSubstring returns the longest common substring between any two input strings (str1 and str2) given two input strings. In this method time complexity is O(n*m), where n and m are the lengths of the input strings.
Example:
Javascript
function findLongestCommonSubstring(str1, str2) { let longestSubstring = ""; for (let i = 0; i < str1.length; i++) { for (let j = 0; j < str2.length; j++) { let substring = ""; let x = i; let y = j; while (x < str1.length && y < str2.length && str1[x] === str2[y]) { substring += str1[x]; x++; y++; } if (substring.length > longestSubstring.length) { longestSubstring = substring; } } } return longestSubstring; } const string1 = "GeeksForneveropen"; const string2 = "Geekscode"; const longestCommonSubstring = findLongestCommonSubstring(string1, string2); console.log("Longest Common Substring:", longestCommonSubstring); |
Longest Common Substring: Geeks
Approach 2: Dynamic Programming
The dynamic programming is the optimised approach of the previous method. In this method we will use 2D array for storing the lengths of common substrings between str1 and str2. In this example, we are creating an LCS table to store the length of the longest common substring ending at that position. After filling the table by iterating through both strings and incrementing the value if the characters match. Then we keep track of the maximum length seen and the corresponding substring and return the longest substring found.
Example:
Javascript
function longestCommonSubstring(str1, str2) { let n = str1.length; let m = str2.length; let lcs = []; for (let i = 0; i <= n; i++) { lcs[i] = []; for (let j = 0; j <= m; j++) { lcs[i][j] = 0; } } let result = ""; let max = 0; for (let i = 0; i < n; i++) { for (let j = 0; j < m; j++) { if (str1[i] === str2[j]) { lcs[i + 1][j + 1] = lcs[i][j] + 1; if (lcs[i + 1][j + 1] > max) { max = lcs[i + 1][j + 1]; result = str1.substring(i - max + 1, i + 1); } } } } return result; } let str1 = "GeeksForneveropen"; let str2 = "Geekscode"; let result = longestCommonSubstring(str1, str2); console.log("Longest Common Substring:", result); |
Longest Common Substring: Geeks
