You are browsing the archive for common.

[JavaScript Quiz #13] Finding longest common substring of strings

April 25, 2015 in JavaScript

Finding the longest common substring of strings is one of the interesting problems. Assume that we have two JavaScript strings like “ababccd” and “abccw”, Can we write a JavaScript utility function that can find the common substrings of these two strings which is “abcc” in this case.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
One of the possible solutions to this problem is to create a 2D comparison array (of size [First string length][Second string length]) which will hold the comparisons between every character in the first and the second strings. If the character of the first string does not match the second string character then set the array cell to 0.
If we find the first string current character matches the second string current character then set the corresponding array cell to 1 but take care if the upper left diagonal cell of the current cell in the comparison array is greater than 0 then you need set the current cell value to the upper left diagonal cell value + 1 (Upper left diagonal cell refers to the previous character of both strings).

Coding this is very simple and the complexity of this code is O(length of the first string * length of the second string) as follows.

var StringUtils = function() {
}

StringUtils.findLongestCommonSubstring = function(string1, string2) {
	var comparsions = []; //2D array for the char comparsions ...
	var maxSubStrLength = 0;
	var lastMaxSubStrIndex = -1, i, j, char1, char2, startIndex;

	for (i = 0; i < string1.length; ++i) {
		comparsions[i] = new Array();

		for (j = 0; j < string2.length; ++j) {
			char1 = string1.charAt(i);
			char2 = string2.charAt(j);

			if (char1 === char2) {
				if (i > 0 && j > 0) {
					comparsions[i][j] = comparsions[i - 1][j - 1] + 1;
				} else {
					comparsions[i][j] = 1;
				}
			} else {
				comparsions[i][j] = 0;
			}

			if (comparsions[i][j] > maxSubStrLength) {
				maxSubStrLength = comparsions[i][j];
				lastMaxSubStrIndex = i;
			}
		}
	}

	if (maxSubStrLength > 0) {
		startIndex = lastMaxSubStrIndex - maxSubStrLength + 1;

		return string1.substr(startIndex, maxSubStrLength);
	}

	return null;
}

// Test code
console.log(StringUtils.findLongestCommonSubstring("ababccd", "abccx"));
console.log(StringUtils.findLongestCommonSubstring("ababccd", "ccxaba"));
console.log(StringUtils.findLongestCommonSubstring("becooltopeople", "topeoplebecool"));    
console.log(StringUtils.findLongestCommonSubstring("ababccd", "zzzz")); 

As shown in the implementation, we store two main items, the maximum common substring length and its last index and thankfully using JavaScript substr function, we can get the desired common substring string. The output will be as follows.

abcc
aba
topeople
null

Finally, note that if you have two longest substrings then this code will get the first of them.

Skip to toolbar