Longest Common Substring

Benchmark created by birjolaxew on April 27, 2015

Preparation HTML

<script>
var StringUtils = {};

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;
}

StringUtils.findLongestCommonSubstring_Quick = function(a,b) {
  var longest = "";
  // loop through the first string
  for (var i = 0; i < a.length; ++i) {
    // loop through the second string
    for (var j = 0; j < b.length; ++j) {
      // if it's the same letter
      if (a[i] === b[j]) {
        var str = a[i];
        var k = 1;
        // keep going until the letters no longer match, or we reached end
        while (i+k < a.length && j+k < b.length // haven't reached end
               && a[i+k] === b[j+k]) { // same letter
          str += a[i+k];
          ++k;
        }
        // if this substring is longer than the longest, save it as the longest
        if (str.length > longest.length) { longest = str }
      }
    }
  }
  return longest;
}
</script>

Test runner

StringUtils.findLongestCommonSubstring("ababccd", "abccx");   
StringUtils.findLongestCommonSubstring("ababccd", "zzzz");
StringUtils.findLongestCommonSubstring("thisisaverylongstringthatisverylongandtestsperformanceonalongstring", "alskdjwioqweouoiuqweqwueiooqiweuioqowuperformancekaw");
StringUtils.findLongestCommonSubstring("thisisaverylongstringthatisverylongandtestsperformanceonalongstring", "zzz");

StringUtils.findLongestCommonSubstring_Quick("ababccd", "abccx");  
StringUtils.findLongestCommonSubstring_Quick("ababccd", "zzzz"); 
StringUtils.findLongestCommonSubstring_Quick("thisisaverylongstringthatisverylongandtestsperformanceonalongstring", "alskdjwioqweouoiuqweqwueiooqiweuioqowuperformancekaw");
StringUtils.findLongestCommonSubstring_Quick("thisisaverylongstringthatisverylongandtestsperformanceonalongstring", "zzz");

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.

• Revision 1: published by birjolaxew on April 27, 2015