searching/longest-common-subsequence.js

  1. (function (exports) {
  2.   'use strict';
  4.   exports.longestCommonSubsequence = (function () {
  6.     /**
  7.      * Find the lengths of longest common sub-sequences
  8.      * of two strings and their substrings.
  9.      *
  10.      * Complexity: O(MN).
  11.      *
  12.      * @private
  13.      * @param {String} first string
  14.      * @param {String} second string
  15.      * @return {Array} two dimensional array with LCS
  16.      * lengths of input strings and their substrings.
  17.      *
  18.      */
  19.     function getLcsLengths(str1, str2) {
  20.       var result = [];
  21.       for (var i = -1; i < str1.length; i = i + 1) {
  22.         result[i] = [];
  23.         for (var j = -1; j < str2.length; j = j + 1) {
  24.           if (i === -1 || j === -1) {
  25.             result[i][j] = 0;
  26.           } else if (str1[i] === str2[j]) {
  27.             result[i][j] = result[i - 1][j - 1] + 1;
  28.           } else {
  29.             result[i][j] = Math.max(result[i - 1][j], result[i][j - 1]);
  30.           }
  31.         }
  32.       }
  33.       return result;
  34.     }
  36.     /**
  37.      * Find longest common sub-sequences of two strings.
  38.      *
  39.      * Complexity: O(M + N).
  40.      *
  41.      * @private
  42.      * @param {String} first string
  43.      * @param {String} second string
  44.      * @return {Array} two dimensional array with LCS
  45.      * lengths of input strings and their substrings
  46.      * returned from 'getLcsLengths' function.
  47.      *
  48.      */
  49.     function getLcs(str1, str2, lcsLengthsMatrix) {
  50.       var execute = function (i, j) {
  51.         if (!lcsLengthsMatrix[i][j]) {
  52.           return '';
  53.         } else if (str1[i] === str2[j]) {
  54.           return execute(i - 1, j - 1) + str1[i];
  55.         } else if (lcsLengthsMatrix[i][j - 1] > lcsLengthsMatrix[i - 1][j]) {
  56.           return execute(i, j - 1);
  57.         } else {
  58.           return execute(i - 1, j);
  59.         }
  60.       };
  61.       return execute(str1.length - 1, str2.length - 1);
  62.     }
  64.     /**
  65.      * Algorithm from dynamic programming. It finds the longest
  66.      * common sub-sequence of two strings. For example for strings 'abcd'
  67.      * and 'axxcda' the longest common sub-sequence is 'acd'.
  68.      *
  69.      * @example
  70.      * var subsequence = require('path-to-algorithms/src/searching/'+
  71.      * 'longest-common-subsequence').longestCommonSubsequence;
  72.      * console.log(subsequence('abcd', 'axxcda'); // 'acd'
  73.      *
  74.      * @public
  75.      * @module searching/longest-common-subsequence
  76.      * @param {String} first input string.
  77.      * @param {String} second input string.
  78.      * @return {Array} Longest common subsequence.
  79.      */
  80.     return function (str1, str2) {
  81.       var lcsLengthsMatrix = getLcsLengths(str1, str2);
  82.       return getLcs(str1, str2, lcsLengthsMatrix);
  83.     };
  84.   })();
  86. })(typeof window === 'undefined' ? module.exports : window);