Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

That's because they all use greedy O(ND) algorithms or equivalent.

But conceptually, no matter what the algorithm, the greediness is usually a requirement to maintaining the theoretical time bound of LCS based algorithms.

Patience trades the time bound for "better" results (patience is worst case O(ND^2).

Histogram is a neatly engineered and extended version of patience with an O(ND) timebound (and in fact, is faster than both myers and patience while providing good patience-like output).



Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: