Wondering what’s next for npm?Check out our public roadmap! »

    js-lcs
    TypeScript icon, indicating that this package has built-in type declarations

    1.0.1 • Public • Published

    js-lcs

    npm version License: MIT Build Status

    Partial1 implementation of Longest common substring problem in TypeScript/JavaScript, relatively fast and memory-optimized2.

    Usage

    Simple

    import { LCS } from 'js-lcs';
     
    LCS.size("aababcabcdabcaba", "eabcde"); // 4

    Advanced

    You can get more performance if you switch to typed arrays like Uint8Array, Uint16Array, and instantiate only one instance of LCS class:

    import { LCS } from 'js-lcs';
     
    const rawFiles = [
      // Uint16Array of char codes in file_1.txt
      // ...
      // Uint16Array of char codes in file_n.txt
    ];
     
    const maxSize = Math.max(...rawFiles.map(f => f.length));
    const lcs = new LCS({ maxSize }); // in this way you reuse once allocated memory for every lcs.size() call
     
    for (let i = 0; i < rawFiles.length; i++) {
      for (let j = 0; j < i; j++) {
          const [a, b] = [rawFiles[j], rawFiles[i]];
          console.log(lcs.size(a, b));
        }
      }
    }

    Please always make sure you don't mix types of arguments to lcs.size(), e.g. if you start passing typed arrays, do not pass strings anymore and vice versa. Otherwise, you risk getting size() function deoptimized by V8.

    Footnotes

    1. At the moment, it can calculate only size of the longest common substring, not the string itself.
    2. Processing two 3,000-char strings takes under 2 seconds, however, memory consumption still can be improved a bit, from O(max(r, n)) to O(min(r, n)) with a little pull request. Performance improvements are very welcome!

    Install

    npm i js-lcs

    DownloadsWeekly Downloads

    3

    Version

    1.0.1

    License

    MIT

    Unpacked Size

    5.53 kB

    Total Files

    11

    Last publish

    Collaborators

    • avatar