Hacker News Reader

Having looked at the code a bit I stumbled onto this:

https://github.com/alexmacarthur/striff/blob/master/src/util...

This... can't be right.

Can you explain how your algorithm differs from, in particular, this one: https://en.wikipedia.org/wiki/Longest_common_subsequence_pro...

Also, why does it differ from that?

View on HN

Aside from the fact that they are basically generating power sets, if you don’t need all the values at once, a better method would be to use a generator function if all you are doing is iterating. That way you don’t need to create all the values in memory first.

A library that I like for this is https://www.npmjs.com/package/generatorics although there may be more modern ones available.

> Aside from the fact that they are basically generating power sets

!

String diff calls for an M x N cost matrix and simple dynamic programming with tail calls (or you can unwind it into loops if you have to).

Not... not power sets.

I would recommend using an optimized permutations library/generator on the string start and end indices instead of directly manipulating the slices.

> permutations

!

Hey, you said it.

I would recommend against permutations

You still need to generate all the permutations, even if you use dynamic programming.

Reply on news.ycombinator.com