JavaScript - Advanced Algorithms(longest common substring, brute-force technique)

Data Structures and Algorithms With Javascript
(O'Reilly Media)
Michael McMillan(著)

開発環境

• OS X El Capitan - Apple (OS)
• Emacs (Text Editor)
• JavaScript (プログラミング言語)
• SpiderMonkey, Node.js(V8) (JavaScript engine)

Data Structures and Algorithms With Javascript (Michael McMillan(著)、O'Reilly Media)のChapter 14(Advanced Algorithms)、Exercises 1.(No. 6550)を解いてみる。

Exercises 1.(No. 6550)

JavaScript(Emacs)

/*jslint         browser : true, continue : true,
  devel  : true, indent  : 4,    maxerr   : 50,
  newcap : true, nomen   : true, plusplus : false,
  regexp : true, sloppy  : true, vars     : false,
  white  : true
*/

/*global */
var lcs;

lcs = function (word1, word2) {
    var str = '',
        i,
        max_i,
        j,
        max_j,
        inner_i,
        inner_j,
        str_temp;

    for (i = 0, max_i = word1.length; i < max_i; i += 1) {
        for (j = 0, max_j = word2.length; j < max_j; j += 1) {
            if (word1[i] === word2[j]) {
                str_temp = word1[i];
                inner_i = i + 1;
                inner_j = j + 1;
                while (inner_i < max_i && inner_j < max_j &&
                       word1[inner_i] === word2[inner_j]) {
                    str_temp += word1[inner_i];
                    inner_i += 1;
                    inner_j += 1;
                }
                if (str_temp.length > str.length) {
                    str = str_temp;
                }
            }
        }
    }
    return str;
};

console.log(lcs('raven', 'havoc') === 'av');
console.log(lcs('abbcc', 'dbbcc') === 'bbcc');
console.log(lcs('abcde', '') === '');
console.log(lcs('abcde', 'a') === 'a');
console.log(lcs('abcde', 'ab') === 'ab');
console.log(lcs('abcde', 'af') === 'a');
console.log(lcs('abcde', 'abf') === 'ab');
console.log(lcs('abcde', 'e') === 'e');
console.log(lcs('abcde', 'fe') === 'e');
console.log(lcs('abcde', 'fde') === 'de');

出力結果(Terminal, shell, SpiderMonkey)

$ jslint sample1.js

sample1.js is OK.
$ node sample1.js
true
true
true
true
true
true
true
true
true
true
$