[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.

Back from ApacheCon North America 2015

I just get back from ApacheCon North America that was be held from 13 April to 16 April @Austin, Texas, USA. The conference organization was really great and there were a lot of attendees in the conference sessions.
IMG_8838

I had the chance to present “Apache Cordova In Action” in 13 April, the session had many attendees and I was really amazed by the energy, enthusiasm, and responsiveness of the attendees during the session.
Feedback

The session went great and I was glad to give a free copy of my JavaScript Mobile Application Development book to one of the attendees who answered a JavaScript quiz at the end of my session.
Books

I uploaded my session below:

Finally, I would like to thank all the organizers of ApacheCon conference for making the conference looks so great.
Main