Giter VIP home page Giter VIP logo

javascript-algorithms's Introduction

Hi there!

I'm Oleksii. I work as a full-time software engineer at Uber. In my spare time I do open-sourcing (normally it is about 1-2 hours in the morning before the work).

Most of my open-source ๐Ÿš€ projects below ๐Ÿ‘‡๐Ÿป are focused on one thing - to help people learn ๐Ÿ“š. You may use these projects to learn about algorithms in JavaScript and get prepared for technical interviews, or to learn Python syntax and start experimenting with machine learning algorithms and math behind them, etc.

There are also other projects that I've developed for fun but that you might find useful, like โœ๐Ÿป okso.app online drawing app.

I also write ๐Ÿ“ articles about life, web-development and machine learning.

Getting in touch

trekhleb.dev

Follow me on Twitter ย  Follow me on LinkedIn ย  Follow me on Medium

javascript-algorithms's People

Contributors

adityahiran avatar agusnavce avatar albertstill avatar alexanderkhivrych avatar applejax avatar austintheriot avatar avi09 avatar bruce-feldman avatar childrentime avatar davidkadaria avatar fveronezipeters avatar iwaskorean avatar jpvg10 avatar kersov avatar m-maksyutin avatar moshejs avatar niltonslf avatar oscarrg avatar petershershov avatar requiresun avatar robtaussig avatar seincorp avatar tapaswenipathak avatar tiendq avatar trekhleb avatar tusba avatar ujjwalaryal avatar vivitruong avatar vladimirschneider avatar yeonjuan avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

javascript-algorithms's Issues

rabinKarp seems to miss some matches

Hello,

I recently tried to run some property based tests on the algorithms provided in javascript-algorithms.
I discovered the following failing case with rabinKarp algorithm:

expect(rabinKarp("^ !/'#'pp", " !/'#'pp")).toBe(2); // output: -1

In order to find it, I used fast-check framework with the property:

// for any strings a, b and c
// rabinKarp(a + b + c, b) should be different from -1 (indeed b is a substring of a+b+c)
fc.assert(
  fc.property(
    fc.string(), fc.string(), fc.string(),
    (a, b, c) => rabinKarp(a + b + c, b) !== -1
  )
);

I was not able to have a smaller example for this precise case :/

Wrong description

Please add correct description for javascript-algorithms/src/data-structures/linked-list/LinkedList.js, because comment in Delete function is misleading:
// If the head must be deleted then make 2nd node to be a head.

It would be better to add:
'while' will delete all nodes with the same value, starting with the this.head.

Add Liu Hui's ฯ€ algorithm

https://en.wikipedia.org/wiki/Liu_Hui's_%CF%80_algorithm

e.g:

const getSideLength = (sideLength, count) => {
  if (count <= 0) return sideLength;
  const m = sideLength / 2;
  const g = Math.sqrt((0.5 ** 2) - (m ** 2));
  const j = 0.5 - g;
  return getSideLength(Math.sqrt((j ** 2) + (m ** 2)), count - 1);
};


const pi = (splitCount = 0) => {
  const sideLength = getSideLength(0.5, splitCount);
  const sideCount = 6 * (splitCount ? 2 ** splitCount : 1);
  return sideLength * sideCount;
};

// for (let i = 0; i < 100; i += 1) {
//   const p = pi(i);
//   console.log(i, p, p === Math.PI);
// }

export default pi;

removeChild in BinaryTreeNode does not remove parent from child

Apologies if this is the expected behavior. In BinaryTreeNode.js, the function removeChild sets either this.left or this.right to null, but does not set nodeToRemove.parent to null. So for example the following test fails:

const rootNode = new BinarySearchTreeNode('foo');
rootNode.insert('bar');
const childNode = rootNode.find('bar');
rootNode.remove('bar');
expect(childNode.parent).toBeNull();

Rename `QuickSortInPlace` to `TrueQuickSort` or something similar.

It should be mentioned that QuickSortInPlace is the actual quick sort. Other implementation that allows using extra space is like quick sort but not the strictly the actual algorithm.

I've seen this at several places. For example the following implementation of quicksort in Haskell

quicksort :: (Ord a) => [a] -> [a]  
quicksort [] = []  
quicksort (x:xs) =   
    let smallerSorted = quicksort [a | a <- xs, a <= x]  
        biggerSorted = quicksort [a | a <- xs, a > x]  
    in  smallerSorted ++ [x] ++ biggerSorted  

It is shown as a quicksort implementation but in reality it is not.
A lot of newbies will get a wrong idea about the quicksort this way who are only learning algos this way.
It should at least be mentioned in the ReadMe that the one with the in-place is the real one.

Translation

Hello, Can I try to translate the repo to Chinese?

Implementing Segment tree

I'm planning to get started on a segment tree implementation. The first step would be to implement Range Min Query, then possibly a generalized implementation.

Z -algorithm

I'm new to open source,I wanted to implement z-algorithm for strings

Translate to korean

Hello!!
I want to translate README into Korean.
Can I?
And, are there any restriction?

What about rope?

I found this repo while looking for a good example of rope. But I can't find one :(

Add B-Tree

I would like to contriblute to adding the B-Tree data structure.
It is a rather common data structure that is great for large data, I'll be glad to implement it.

bug in AVL tree rotateLeftRight and rotateRightLeft

in rotateLeftRight, while leftRightNode has left child, it will be lost.
also as well rotateRightLeft.

the following code is my correction.

 rotateLeftRight(rootNode) {
    // Detach left node from rootNode since it is going to be replaced.
    const leftNode = rootNode.left;
    rootNode.setLeft(null);

    // Detach right node from leftNode.
    const leftRightNode = leftNode.right;
    leftNode.setRight(null);

    if (leftRightNode.left) {
      leftNode.setRight(leftRightNode.left);
      leftRightNode.setLeft(null);
    }

    // Attach leftRightNode to the rootNode.
    rootNode.setLeft(leftRightNode);

    // Attach leftNode as left node for leftRight node.
    leftRightNode.setLeft(leftNode);

    // Do left-left rotation.
    this.rotateLeftLeft(rootNode);
  }
  rotateRightLeft(rootNode) {
    // Detach right node from rootNode since it is going to be replaced.
    const rightNode = rootNode.right;
    rootNode.setRight(null);

    // Detach left node from rightNode.
    const rightLeftNode = rightNode.left;
    rightNode.setLeft(null);

    if (rightLeftNode.right) {
      rightNode.setLeft(rightLeftNode.right);
      rightLeftNode.setRight(null);
    }

    // Attach rightLeftNode to the rootNode.
    rootNode.setRight(rightLeftNode);

    // Attach rightNode as right node for rightLeft node.
    rightLeftNode.setRight(rightNode);

    // Do right-right rotation.
    this.rotateRightRight(rootNode);
  }

A suggestion about Factorial

Not an issue - more of a suggestion. Is it better to start the loop from 2๏ผŸ

export default function factorial(number) {
  let result = 1;

  for (let i = 2; i <= number; i += 1) {
    result *= i;
  }

  return result;
}

Fibonacci sequences

Not an issue - more of a suggestion. Would be good to return an array for the fibonacci sequence, as well as the sequence at nth position (and maybe rename the nth-position fibonacciNth() or something). For example:

export default function fibonacci(steps) {
  const fibSequence = [];

  let currentValue = 1;
  let previousValue = 0;

  if(steps === 1) {
    return [1];
  }

  while(steps--) {
    currentValue += previousValue;
    previousValue = (currentValue - previousValue);

    fibSequence.push(currentValue);
  }

  return fibSequence;
}

And:

export default function fibonacciNth(steps) {
  let currentValue = 1;
  let previousValue = 0;

  if(steps === 1) {
    return 1;
  }

  while(steps--) {
    currentValue += previousValue;
    previousValue = (currentValue - previousValue);
  }

  return currentValue;
}

Also, where before there was a:

while(iterationsCounter) {
  // Do code
  
  iterationsCounter -= 1;
}

This is mildly verbose, and can be more succinctly written without detriment to legibility as:

while(iterationsCounter--) {
  // Do code
}

Personally I think that's more readable. Happy to do a PR?

Edit: camel cased variable names to match existing code

Combination without repetition algorithm difficult to understand

##I found the algorithm is so hard to understand that I almost pulled my hairs off. I tried to analyze it in Python tutor but It didn't get easier. After struggling for a few hours, I figured a solution that is more expressive and easier to understand.

function comboWithoutRepeat(chooseFrom, numChosen) {
  const combinations = []
  function recursive(chooseFrom, numChosen, path = []) {
    if (numChosen === 0) {
      combinations.push(path)
      return
    }
    for (let i = 0; i <= chooseFrom.length - numChosen; i++) {
      const letter = chooseFrom[i]
      const rest = chooseFrom.slice(i + 1)
      recursive(rest, numChosen - 1, [letter].concat(path))
    }
  }
  recursive(chooseFrom, numChosen)
  return combinations
}

console.log(comboWithoutRepeat([1, 2, 3, 4], 3, ''))

Collision resolution in hash-table

In the HashTable implementation currently there is no collision resolution mechanism. The following insertion method updates the existing node. There can be chaining or open addressing methods implemented.

  insert(key, value) {
    const bucketLinkedList = this.buckets[this.hash(key)];
    const node = bucketLinkedList.find({ callback: nodeValue => nodeValue.key === key });

    if (!node) {
      // Insert new node.
      bucketLinkedList.append({ key, value });
    } else {
      // Update value of existing node.
      node.value.value = value;
    }
  }  

My concern about no classification by Procedural/Imperative and Functional programming Paradigm

Hi, this is a great project. Thanks.
I have a concern that I would like to share.

For instance, looking at /algorithms/math/factorial which is one of the most basic math topic:
https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/factorial

I found 2 implementations:

factorial.js

export default function factorial(number) {
  let result = 1;

  for (let i = 2; i <= number; i += 1) {
    result *= i;
  }

  return result;
}

factorialRecursive.js

export default function factorialRecursive(number) {
  return number > 1 ? number * factorialRecursive(number - 1) : 1;
}

factorial.js is a code of Procedural/Imperative programming style, and uses mutable variables.

factorialRecursive.js is recursive, and can be said functional programming style, immutable. Alghouth this is a typical implementation which I can see everywhere, in terms of "Big O notations". this is rather anti-pattern.

A better or I would say, a proper way is,

factorialFunctional.js

//[...Array(5).keys()]
//-> [ 0, 1, 2, 3 ,4 ]

const natural = n => {
    const arr0 = [...Array(n + 1).keys()];
    const [first, ...arr] = arr0;
    return arr;
};

console.log(
    natural(5) //[ 1, 2, 3, 4, 5 ]
);

function factorialFunctional(number) {
    const list = number < 1
        ? [1]
        : natural(number)
    const multiply = (a, b) => a * b;
    return list.reduce(multiply);
}

console.log(
    factorialFunctional(5)//120
);

This is as efficient as the factorial.js in terms of "Big O notations", and immutable.

I think when algorithms are presented, it's significantly important to clarify what kind of programming paradigm the algorithms are based on.

Currently, it seems the contributions are updated randomly without formal classification for them, and I think it's a good idea to show a guideline in the README that to clarify which paradigm every algorithm belongs to. In this manner, a contributors notice "oh, here, there is no Functional or Imperative pattern yet, so I will add.."

Thanks.

the picture about Red-Black Tree is not match

see javascript-algorithms/src/data-structures/tree/red-black-tree/readme.md
There are four pictures describe the red-black tree's four cases(LL /LR /RR /RL).But the Right Right Case and the Right Left Case 's picture are the same.

Grouping algorithms for studying

Thank you for creating this repo, it's awesome.
I just have one small question, can you divide all algorithms into group of level like: Beginner, Intermediate, Advance , etc so someone like students or newbies know where to start?

AVL tree does not rebalance after removal

Hi! Thanks for your project. I can't seem to find the removal algorithm in AVL tree: if it simply borrows the binary tree removal, it's incomplete. I was particularly interested in that, cause I have been looking for a removal procedure that doesn't mutate the nodes.

Cheers.

Trie - remove words

Removing words in a Trie seems equally important as adding words. It would be nice to have that.

Test suite failed to run on Ubuntu

Test suite failed to run

SecurityError: localStorage is not available for opaque origins

  at Window.get localStorage [as localStorage] (node_modules/jsdom/lib/jsdom/browser/Window.js:257:15)
      at Array.forEach (<anonymous>)

automated test suite

a suggestion for improve quality, readability and robustness of the algorithms is to have test cases.

without tests it is hard to know if the algorithms / data structure works as intended.

Translate to Spanish

I believe it would be nice to translate the README.md to Spanish and would love to help!

removal from linkedlist

"This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration." - Not correct for removal. Deleting a node from a linked list is not efficient as you have to traverse the list (in case it is very large list then it will not be optimal) The option is to use Vector.

TSP or TPP Algorithm

I'm looking for any implementation of Multiple Travelers Purchase Problem, any idea ?

A* algorithm?

Hey! This repo is awesome! Nice job!

While I was reading through the algorithms, I found weird that the A* algorithm was missing, which is one of the few I know.

I'm just gonna leave this as a suggestion, sorry if I can't do a pull request!

Add Red Black Tree

Hello,

I have once write Red Black Tree in Java and interesting to write another version in Javascript. Anyone have already working on it? If no one, maybe I will pull the Red Black Tree tonight.

Regard,
Hafidz

Add another section

You've created a wonderful repository!
It's really interesting, especially for learning purposes, like in my case.

What do you think about adding a new section that explains how to calculate 3D geometry functions?

Workshopper

How about creating a workshopper? I would love to create one.

Add Max Heap?

A Max Heap DS would be terrific in this repo. Should I work on it and submit a PR? I'm also open to other DS or algorithm contributions.

I'm not sure what this is called or if it belongs here

Hey, I apologize in advance if this is misplaced. I don't have any maths education or know anything of algorithms.

I've been working on something that I believe I misconstrued from a problem I saw asked that dealt with binary trees. I don't know if this is a valid algorithm or not:

// Find all subtrees of n-ary tree. For example:
//
//          1
//        /   \
//       /     \
//      2       3
//     / \     /|\
//    4   6   5 7 8
//       / \
//      9  10
       
// I want to show all subtrees:

// 1    1   1       1       1        1         1
//     /     \     / \     / \      / \         \
//    2       3   2   3   2   3    2   3         3
//                        |        |  /         /
//                        4        4 5         5

I think essentially what I'm trying to communicate here is any valid branching path/"state" from the tree starting at the root node. I first tried order-specific (all permutations of each "level" were valid) but this was far too difficult and I've since retreated to trying to figure out order-inspecific. I could be way off, but this appears to work:

https://repl.it/@GavinRay97/VivaciousWarmheartedComputers-1

Console Output of Trees - CLICK TO EXPAND

var exampleTree = {
  a: {
    b: {
      d: null,
      e: {
        f: null,
        g: {
          i: {
            l: null,
            m: null,
            n: null,
          },
          k: null,
        },
        h: null
      }
    },
    c: null,
    o: null
  },
}

"a -> b"
"a -> b-c"
"a -> b-c -> d"
"a -> b-c -> d-e"
"a -> b-c -> d-e -> f"
"a -> b-c -> d-e -> f-g"
"a -> b-c -> d-e -> f-g-h"
"a -> b-c -> d-e -> f-g-h -> i"
"a -> b-c -> d-e -> f-g-h -> i-k"
"a -> b-c -> d-e -> f-g-h -> i-k -> l"
"a -> b-c -> d-e -> f-g-h -> i-k -> l-m"
"a -> b-c -> d-e -> f-g-h -> i-k -> l-m-n"
"a -> b-c -> d-e -> f-g-h -> i-k -> m"
"a -> b-c -> d-e -> f-g-h -> i-k -> m-n"
"a -> b-c -> d-e -> f-g-h -> i-k -> n"
"a -> b-c -> d-e -> f-g-h -> i -> l"
"a -> b-c -> d-e -> f-g-h -> i -> l-m"
"a -> b-c -> d-e -> f-g-h -> i -> l-m-n"
"a -> b-c -> d-e -> f-g-h -> i -> m"
"a -> b-c -> d-e -> f-g-h -> i -> m-n"
"a -> b-c -> d-e -> f-g-h -> i -> n"
"a -> b-c -> d-e -> f-g-h -> k"
"a -> b-c -> d-e -> f-g -> i"
"a -> b-c -> d-e -> f-g -> i-k"
"a -> b-c -> d-e -> f-g -> i-k -> l"
"a -> b-c -> d-e -> f-g -> i-k -> l-m"
"a -> b-c -> d-e -> f-g -> i-k -> l-m-n"
"a -> b-c -> d-e -> f-g -> i-k -> m"
"a -> b-c -> d-e -> f-g -> i-k -> m-n"
"a -> b-c -> d-e -> f-g -> i-k -> n"
"a -> b-c -> d-e -> f-g -> i -> l"
"a -> b-c -> d-e -> f-g -> i -> l-m"
"a -> b-c -> d-e -> f-g -> i -> l-m-n"
"a -> b-c -> d-e -> f-g -> i -> m"
"a -> b-c -> d-e -> f-g -> i -> m-n"
"a -> b-c -> d-e -> f-g -> i -> n"
"a -> b-c -> d-e -> f-g -> k"
"a -> b-c -> d-e -> g"
"a -> b-c -> d-e -> g-h"
"a -> b-c -> d-e -> g-h -> i"
"a -> b-c -> d-e -> g-h -> i-k"
"a -> b-c -> d-e -> g-h -> i-k -> l"
"a -> b-c -> d-e -> g-h -> i-k -> l-m"
"a -> b-c -> d-e -> g-h -> i-k -> l-m-n"
"a -> b-c -> d-e -> g-h -> i-k -> m"
"a -> b-c -> d-e -> g-h -> i-k -> m-n"
"a -> b-c -> d-e -> g-h -> i-k -> n"
"a -> b-c -> d-e -> g-h -> i -> l"
"a -> b-c -> d-e -> g-h -> i -> l-m"
"a -> b-c -> d-e -> g-h -> i -> l-m-n"
"a -> b-c -> d-e -> g-h -> i -> m"
"a -> b-c -> d-e -> g-h -> i -> m-n"
"a -> b-c -> d-e -> g-h -> i -> n"
"a -> b-c -> d-e -> g-h -> k"
"a -> b-c -> d-e -> g -> i"
"a -> b-c -> d-e -> g -> i-k"
"a -> b-c -> d-e -> g -> i-k -> l"
"a -> b-c -> d-e -> g -> i-k -> l-m"
"a -> b-c -> d-e -> g -> i-k -> l-m-n"
"a -> b-c -> d-e -> g -> i-k -> m"
"a -> b-c -> d-e -> g -> i-k -> m-n"
"a -> b-c -> d-e -> g -> i-k -> n"
"a -> b-c -> d-e -> g -> i -> l"
"a -> b-c -> d-e -> g -> i -> l-m"
"a -> b-c -> d-e -> g -> i -> l-m-n"
"a -> b-c -> d-e -> g -> i -> m"
"a -> b-c -> d-e -> g -> i -> m-n"
"a -> b-c -> d-e -> g -> i -> n"
"a -> b-c -> d-e -> g -> k"
"a -> b-c -> d-e -> h"
"a -> b-c -> e"
"a -> b-c -> e -> f"
"a -> b-c -> e -> f-g"
"a -> b-c -> e -> f-g-h"
"a -> b-c -> e -> f-g-h -> i"
"a -> b-c -> e -> f-g-h -> i-k"
"a -> b-c -> e -> f-g-h -> i-k -> l"
"a -> b-c -> e -> f-g-h -> i-k -> l-m"
"a -> b-c -> e -> f-g-h -> i-k -> l-m-n"
"a -> b-c -> e -> f-g-h -> i-k -> m"
"a -> b-c -> e -> f-g-h -> i-k -> m-n"
"a -> b-c -> e -> f-g-h -> i-k -> n"
"a -> b-c -> e -> f-g-h -> i -> l"
"a -> b-c -> e -> f-g-h -> i -> l-m"
"a -> b-c -> e -> f-g-h -> i -> l-m-n"
"a -> b-c -> e -> f-g-h -> i -> m"
"a -> b-c -> e -> f-g-h -> i -> m-n"
"a -> b-c -> e -> f-g-h -> i -> n"
"a -> b-c -> e -> f-g-h -> k"
"a -> b-c -> e -> f-g -> i"
"a -> b-c -> e -> f-g -> i-k"
"a -> b-c -> e -> f-g -> i-k -> l"
"a -> b-c -> e -> f-g -> i-k -> l-m"
"a -> b-c -> e -> f-g -> i-k -> l-m-n"
"a -> b-c -> e -> f-g -> i-k -> m"
"a -> b-c -> e -> f-g -> i-k -> m-n"
"a -> b-c -> e -> f-g -> i-k -> n"
"a -> b-c -> e -> f-g -> i -> l"
"a -> b-c -> e -> f-g -> i -> l-m"
"a -> b-c -> e -> f-g -> i -> l-m-n"
"a -> b-c -> e -> f-g -> i -> m"
"a -> b-c -> e -> f-g -> i -> m-n"
"a -> b-c -> e -> f-g -> i -> n"
"a -> b-c -> e -> f-g -> k"
"a -> b-c -> e -> g"
"a -> b-c -> e -> g-h"
"a -> b-c -> e -> g-h -> i"
"a -> b-c -> e -> g-h -> i-k"
"a -> b-c -> e -> g-h -> i-k -> l"
"a -> b-c -> e -> g-h -> i-k -> l-m"
"a -> b-c -> e -> g-h -> i-k -> l-m-n"
"a -> b-c -> e -> g-h -> i-k -> m"
"a -> b-c -> e -> g-h -> i-k -> m-n"
"a -> b-c -> e -> g-h -> i-k -> n"
"a -> b-c -> e -> g-h -> i -> l"
"a -> b-c -> e -> g-h -> i -> l-m"
"a -> b-c -> e -> g-h -> i -> l-m-n"
"a -> b-c -> e -> g-h -> i -> m"
"a -> b-c -> e -> g-h -> i -> m-n"
"a -> b-c -> e -> g-h -> i -> n"
"a -> b-c -> e -> g-h -> k"
"a -> b-c -> e -> g -> i"
"a -> b-c -> e -> g -> i-k"
"a -> b-c -> e -> g -> i-k -> l"
"a -> b-c -> e -> g -> i-k -> l-m"
"a -> b-c -> e -> g -> i-k -> l-m-n"
"a -> b-c -> e -> g -> i-k -> m"
"a -> b-c -> e -> g -> i-k -> m-n"
"a -> b-c -> e -> g -> i-k -> n"
"a -> b-c -> e -> g -> i -> l"
"a -> b-c -> e -> g -> i -> l-m"
"a -> b-c -> e -> g -> i -> l-m-n"
"a -> b-c -> e -> g -> i -> m"
"a -> b-c -> e -> g -> i -> m-n"
"a -> b-c -> e -> g -> i -> n"
"a -> b-c -> e -> g -> k"
"a -> b-c -> e -> h"
"a -> b-c-o"
"a -> b-c-o -> d"
"a -> b-c-o -> d-e"
"a -> b-c-o -> d-e -> f"
"a -> b-c-o -> d-e -> f-g"
"a -> b-c-o -> d-e -> f-g-h"
"a -> b-c-o -> d-e -> f-g-h -> i"
"a -> b-c-o -> d-e -> f-g-h -> i-k"
"a -> b-c-o -> d-e -> f-g-h -> i-k -> l"
"a -> b-c-o -> d-e -> f-g-h -> i-k -> l-m"
"a -> b-c-o -> d-e -> f-g-h -> i-k -> l-m-n"
"a -> b-c-o -> d-e -> f-g-h -> i-k -> m"
"a -> b-c-o -> d-e -> f-g-h -> i-k -> m-n"
"a -> b-c-o -> d-e -> f-g-h -> i-k -> n"
"a -> b-c-o -> d-e -> f-g-h -> i -> l"
"a -> b-c-o -> d-e -> f-g-h -> i -> l-m"
"a -> b-c-o -> d-e -> f-g-h -> i -> l-m-n"
"a -> b-c-o -> d-e -> f-g-h -> i -> m"
"a -> b-c-o -> d-e -> f-g-h -> i -> m-n"
"a -> b-c-o -> d-e -> f-g-h -> i -> n"
"a -> b-c-o -> d-e -> f-g-h -> k"
"a -> b-c-o -> d-e -> f-g -> i"
"a -> b-c-o -> d-e -> f-g -> i-k"
"a -> b-c-o -> d-e -> f-g -> i-k -> l"
"a -> b-c-o -> d-e -> f-g -> i-k -> l-m"
"a -> b-c-o -> d-e -> f-g -> i-k -> l-m-n"
"a -> b-c-o -> d-e -> f-g -> i-k -> m"
"a -> b-c-o -> d-e -> f-g -> i-k -> m-n"
"a -> b-c-o -> d-e -> f-g -> i-k -> n"
"a -> b-c-o -> d-e -> f-g -> i -> l"
"a -> b-c-o -> d-e -> f-g -> i -> l-m"
"a -> b-c-o -> d-e -> f-g -> i -> l-m-n"
"a -> b-c-o -> d-e -> f-g -> i -> m"
"a -> b-c-o -> d-e -> f-g -> i -> m-n"
"a -> b-c-o -> d-e -> f-g -> i -> n"
"a -> b-c-o -> d-e -> f-g -> k"
"a -> b-c-o -> d-e -> g"
"a -> b-c-o -> d-e -> g-h"
"a -> b-c-o -> d-e -> g-h -> i"
"a -> b-c-o -> d-e -> g-h -> i-k"
"a -> b-c-o -> d-e -> g-h -> i-k -> l"
"a -> b-c-o -> d-e -> g-h -> i-k -> l-m"
"a -> b-c-o -> d-e -> g-h -> i-k -> l-m-n"
"a -> b-c-o -> d-e -> g-h -> i-k -> m"
"a -> b-c-o -> d-e -> g-h -> i-k -> m-n"
"a -> b-c-o -> d-e -> g-h -> i-k -> n"
"a -> b-c-o -> d-e -> g-h -> i -> l"
"a -> b-c-o -> d-e -> g-h -> i -> l-m"
"a -> b-c-o -> d-e -> g-h -> i -> l-m-n"
"a -> b-c-o -> d-e -> g-h -> i -> m"
"a -> b-c-o -> d-e -> g-h -> i -> m-n"
"a -> b-c-o -> d-e -> g-h -> i -> n"
"a -> b-c-o -> d-e -> g-h -> k"
"a -> b-c-o -> d-e -> g -> i"
"a -> b-c-o -> d-e -> g -> i-k"
"a -> b-c-o -> d-e -> g -> i-k -> l"
"a -> b-c-o -> d-e -> g -> i-k -> l-m"
"a -> b-c-o -> d-e -> g -> i-k -> l-m-n"
"a -> b-c-o -> d-e -> g -> i-k -> m"
"a -> b-c-o -> d-e -> g -> i-k -> m-n"
"a -> b-c-o -> d-e -> g -> i-k -> n"
"a -> b-c-o -> d-e -> g -> i -> l"
"a -> b-c-o -> d-e -> g -> i -> l-m"
"a -> b-c-o -> d-e -> g -> i -> l-m-n"
"a -> b-c-o -> d-e -> g -> i -> m"
"a -> b-c-o -> d-e -> g -> i -> m-n"
"a -> b-c-o -> d-e -> g -> i -> n"
"a -> b-c-o -> d-e -> g -> k"
"a -> b-c-o -> d-e -> h"
"a -> b-c-o -> e"
"a -> b-c-o -> e -> f"
"a -> b-c-o -> e -> f-g"
"a -> b-c-o -> e -> f-g-h"
"a -> b-c-o -> e -> f-g-h -> i"
"a -> b-c-o -> e -> f-g-h -> i-k"
"a -> b-c-o -> e -> f-g-h -> i-k -> l"
"a -> b-c-o -> e -> f-g-h -> i-k -> l-m"
"a -> b-c-o -> e -> f-g-h -> i-k -> l-m-n"
"a -> b-c-o -> e -> f-g-h -> i-k -> m"
"a -> b-c-o -> e -> f-g-h -> i-k -> m-n"
"a -> b-c-o -> e -> f-g-h -> i-k -> n"
"a -> b-c-o -> e -> f-g-h -> i -> l"
"a -> b-c-o -> e -> f-g-h -> i -> l-m"
"a -> b-c-o -> e -> f-g-h -> i -> l-m-n"
"a -> b-c-o -> e -> f-g-h -> i -> m"
"a -> b-c-o -> e -> f-g-h -> i -> m-n"
"a -> b-c-o -> e -> f-g-h -> i -> n"
"a -> b-c-o -> e -> f-g-h -> k"
"a -> b-c-o -> e -> f-g -> i"
"a -> b-c-o -> e -> f-g -> i-k"
"a -> b-c-o -> e -> f-g -> i-k -> l"
"a -> b-c-o -> e -> f-g -> i-k -> l-m"
"a -> b-c-o -> e -> f-g -> i-k -> l-m-n"
"a -> b-c-o -> e -> f-g -> i-k -> m"
"a -> b-c-o -> e -> f-g -> i-k -> m-n"
"a -> b-c-o -> e -> f-g -> i-k -> n"
"a -> b-c-o -> e -> f-g -> i -> l"
"a -> b-c-o -> e -> f-g -> i -> l-m"
"a -> b-c-o -> e -> f-g -> i -> l-m-n"
"a -> b-c-o -> e -> f-g -> i -> m"
"a -> b-c-o -> e -> f-g -> i -> m-n"
"a -> b-c-o -> e -> f-g -> i -> n"
"a -> b-c-o -> e -> f-g -> k"
"a -> b-c-o -> e -> g"
"a -> b-c-o -> e -> g-h"
"a -> b-c-o -> e -> g-h -> i"
"a -> b-c-o -> e -> g-h -> i-k"
"a -> b-c-o -> e -> g-h -> i-k -> l"
"a -> b-c-o -> e -> g-h -> i-k -> l-m"
"a -> b-c-o -> e -> g-h -> i-k -> l-m-n"
"a -> b-c-o -> e -> g-h -> i-k -> m"
"a -> b-c-o -> e -> g-h -> i-k -> m-n"
"a -> b-c-o -> e -> g-h -> i-k -> n"
"a -> b-c-o -> e -> g-h -> i -> l"
"a -> b-c-o -> e -> g-h -> i -> l-m"
"a -> b-c-o -> e -> g-h -> i -> l-m-n"
"a -> b-c-o -> e -> g-h -> i -> m"
"a -> b-c-o -> e -> g-h -> i -> m-n"
"a -> b-c-o -> e -> g-h -> i -> n"
"a -> b-c-o -> e -> g-h -> k"
"a -> b-c-o -> e -> g -> i"
"a -> b-c-o -> e -> g -> i-k"
"a -> b-c-o -> e -> g -> i-k -> l"
"a -> b-c-o -> e -> g -> i-k -> l-m"
"a -> b-c-o -> e -> g -> i-k -> l-m-n"
"a -> b-c-o -> e -> g -> i-k -> m"
"a -> b-c-o -> e -> g -> i-k -> m-n"
"a -> b-c-o -> e -> g -> i-k -> n"
"a -> b-c-o -> e -> g -> i -> l"
"a -> b-c-o -> e -> g -> i -> l-m"
"a -> b-c-o -> e -> g -> i -> l-m-n"
"a -> b-c-o -> e -> g -> i -> m"
"a -> b-c-o -> e -> g -> i -> m-n"
"a -> b-c-o -> e -> g -> i -> n"
"a -> b-c-o -> e -> g -> k"
"a -> b-c-o -> e -> h"
"a -> b -> d"
"a -> b -> d-e"
"a -> b -> d-e -> f"
"a -> b -> d-e -> f-g"
"a -> b -> d-e -> f-g-h"
"a -> b -> d-e -> f-g-h -> i"
"a -> b -> d-e -> f-g-h -> i-k"
"a -> b -> d-e -> f-g-h -> i-k -> l"
"a -> b -> d-e -> f-g-h -> i-k -> l-m"
"a -> b -> d-e -> f-g-h -> i-k -> l-m-n"
"a -> b -> d-e -> f-g-h -> i-k -> m"
"a -> b -> d-e -> f-g-h -> i-k -> m-n"
"a -> b -> d-e -> f-g-h -> i-k -> n"
"a -> b -> d-e -> f-g-h -> i -> l"
"a -> b -> d-e -> f-g-h -> i -> l-m"
"a -> b -> d-e -> f-g-h -> i -> l-m-n"
"a -> b -> d-e -> f-g-h -> i -> m"
"a -> b -> d-e -> f-g-h -> i -> m-n"
"a -> b -> d-e -> f-g-h -> i -> n"
"a -> b -> d-e -> f-g-h -> k"
"a -> b -> d-e -> f-g -> i"
"a -> b -> d-e -> f-g -> i-k"
"a -> b -> d-e -> f-g -> i-k -> l"
"a -> b -> d-e -> f-g -> i-k -> l-m"
"a -> b -> d-e -> f-g -> i-k -> l-m-n"
"a -> b -> d-e -> f-g -> i-k -> m"
"a -> b -> d-e -> f-g -> i-k -> m-n"
"a -> b -> d-e -> f-g -> i-k -> n"
"a -> b -> d-e -> f-g -> i -> l"
"a -> b -> d-e -> f-g -> i -> l-m"
"a -> b -> d-e -> f-g -> i -> l-m-n"
"a -> b -> d-e -> f-g -> i -> m"
"a -> b -> d-e -> f-g -> i -> m-n"
"a -> b -> d-e -> f-g -> i -> n"
"a -> b -> d-e -> f-g -> k"
"a -> b -> d-e -> g"
"a -> b -> d-e -> g-h"
"a -> b -> d-e -> g-h -> i"
"a -> b -> d-e -> g-h -> i-k"
"a -> b -> d-e -> g-h -> i-k -> l"
"a -> b -> d-e -> g-h -> i-k -> l-m"
"a -> b -> d-e -> g-h -> i-k -> l-m-n"
"a -> b -> d-e -> g-h -> i-k -> m"
"a -> b -> d-e -> g-h -> i-k -> m-n"
"a -> b -> d-e -> g-h -> i-k -> n"
"a -> b -> d-e -> g-h -> i -> l"
"a -> b -> d-e -> g-h -> i -> l-m"
"a -> b -> d-e -> g-h -> i -> l-m-n"
"a -> b -> d-e -> g-h -> i -> m"
"a -> b -> d-e -> g-h -> i -> m-n"
"a -> b -> d-e -> g-h -> i -> n"
"a -> b -> d-e -> g-h -> k"
"a -> b -> d-e -> g -> i"
"a -> b -> d-e -> g -> i-k"
"a -> b -> d-e -> g -> i-k -> l"
"a -> b -> d-e -> g -> i-k -> l-m"
"a -> b -> d-e -> g -> i-k -> l-m-n"
"a -> b -> d-e -> g -> i-k -> m"
"a -> b -> d-e -> g -> i-k -> m-n"
"a -> b -> d-e -> g -> i-k -> n"
"a -> b -> d-e -> g -> i -> l"
"a -> b -> d-e -> g -> i -> l-m"
"a -> b -> d-e -> g -> i -> l-m-n"
"a -> b -> d-e -> g -> i -> m"
"a -> b -> d-e -> g -> i -> m-n"
"a -> b -> d-e -> g -> i -> n"
"a -> b -> d-e -> g -> k"
"a -> b -> d-e -> h"
"a -> b -> e"
"a -> b -> e -> f"
"a -> b -> e -> f-g"
"a -> b -> e -> f-g-h"
"a -> b -> e -> f-g-h -> i"
"a -> b -> e -> f-g-h -> i-k"
"a -> b -> e -> f-g-h -> i-k -> l"
"a -> b -> e -> f-g-h -> i-k -> l-m"
"a -> b -> e -> f-g-h -> i-k -> l-m-n"
"a -> b -> e -> f-g-h -> i-k -> m"
"a -> b -> e -> f-g-h -> i-k -> m-n"
"a -> b -> e -> f-g-h -> i-k -> n"
"a -> b -> e -> f-g-h -> i -> l"
"a -> b -> e -> f-g-h -> i -> l-m"
"a -> b -> e -> f-g-h -> i -> l-m-n"
"a -> b -> e -> f-g-h -> i -> m"
"a -> b -> e -> f-g-h -> i -> m-n"
"a -> b -> e -> f-g-h -> i -> n"
"a -> b -> e -> f-g-h -> k"
"a -> b -> e -> f-g -> i"
"a -> b -> e -> f-g -> i-k"
"a -> b -> e -> f-g -> i-k -> l"
"a -> b -> e -> f-g -> i-k -> l-m"
"a -> b -> e -> f-g -> i-k -> l-m-n"
"a -> b -> e -> f-g -> i-k -> m"
"a -> b -> e -> f-g -> i-k -> m-n"
"a -> b -> e -> f-g -> i-k -> n"
"a -> b -> e -> f-g -> i -> l"
"a -> b -> e -> f-g -> i -> l-m"
"a -> b -> e -> f-g -> i -> l-m-n"
"a -> b -> e -> f-g -> i -> m"
"a -> b -> e -> f-g -> i -> m-n"
"a -> b -> e -> f-g -> i -> n"
"a -> b -> e -> f-g -> k"
"a -> b -> e -> g"
"a -> b -> e -> g-h"
"a -> b -> e -> g-h -> i"
"a -> b -> e -> g-h -> i-k"
"a -> b -> e -> g-h -> i-k -> l"
"a -> b -> e -> g-h -> i-k -> l-m"
"a -> b -> e -> g-h -> i-k -> l-m-n"
"a -> b -> e -> g-h -> i-k -> m"
"a -> b -> e -> g-h -> i-k -> m-n"
"a -> b -> e -> g-h -> i-k -> n"
"a -> b -> e -> g-h -> i -> l"
"a -> b -> e -> g-h -> i -> l-m"
"a -> b -> e -> g-h -> i -> l-m-n"
"a -> b -> e -> g-h -> i -> m"
"a -> b -> e -> g-h -> i -> m-n"
"a -> b -> e -> g-h -> i -> n"
"a -> b -> e -> g-h -> k"
"a -> b -> e -> g -> i"
"a -> b -> e -> g -> i-k"
"a -> b -> e -> g -> i-k -> l"
"a -> b -> e -> g -> i-k -> l-m"
"a -> b -> e -> g -> i-k -> l-m-n"
"a -> b -> e -> g -> i-k -> m"
"a -> b -> e -> g -> i-k -> m-n"
"a -> b -> e -> g -> i-k -> n"
"a -> b -> e -> g -> i -> l"
"a -> b -> e -> g -> i -> l-m"
"a -> b -> e -> g -> i -> l-m-n"
"a -> b -> e -> g -> i -> m"
"a -> b -> e -> g -> i -> m-n"
"a -> b -> e -> g -> i -> n"
"a -> b -> e -> g -> k"
"a -> b -> e -> h"
"a -> c"
"a -> c-o"
"a -> o"
Results (plus head node):  412


Could anyone tell me whether the problem I'm describing is a real/existing algorithm, and how bad/far off my solution is so far? It's probably O(n^10) or something ridiculous too.

Thank you!

Longest common substring does not handle unicode properly

It seems that the algorithm longestCommonSubstring does not handle unicode characters properly:

longestCommonSubstr('๐Œต๐Œต**ABC', '๐Œต๐Œต--ABC') === '๐Œต๐Œต'
// whereas the longest one should be ABC (in terms of number of code points)

// Number of code points:
[...'๐Œต๐Œต'].length === 2
[...'ABC'].length === 3

// Number of "characters":
'๐Œต๐Œต'.length === 4
'ABC'.length === 3

You should maybe add a note on the algorithm regarding this. Basically the problem can occur whenever the strings contain characters outside the BMP range (ie code points greater than 0xffff).

Feel free to close the issue whenever you want. The aim was just to signal the problem is case you want to patch it in a way.

Translate to russian

Hello.

I want to translate all README into Russian, are there any rules for translation?

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.