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

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.

This entry was posted in JavaScript and tagged , , , , , by Hazem Saleh. Bookmark the permalink.

About Hazem Saleh

Hazem Saleh has more than eleven years of experience in Cloud, Mobile and Open Source technologies. He worked as a software engineer, technical leader, application architect, and technical consultant for many clients around the world. He is an Apache PMC (Project Management Committee) member and a person who spent many years of his life writing open source software. Beside being the author of the "JavaScript Unit Testing" book, "JavaScript Mobile Application Development" book, "Pro JSF and HTML5" book and the co-author of the "Definitive guide to Apache MyFaces" book, Hazem is also an author of many technical articles, a developerWorks contributing author and a technical speaker in both local and international conferences such as ApacheCon North America, Geecon, JavaLand, JSFDays, CON-FESS Vienna and JavaOne. Hazem is an XIBMer, he worked in IBM for ten years. Now, He is working for Nickelodeon New York as a Mobile Architect. He is also an OpenGroup Master Certified Specialist.