News for hackers. Stuff that matters.

A comment on Binary Decision Diagrams (2010). Parent comment

Re:Binary Decision Diagrams (2010) by froh on Wednesday December 09, 2020 @11:50AM (#25360617)
Suffix Arrays: with their meanwhile linear time construction they allow for very efficient pattern matching, indexing and more efficient compression algorithms. (introduced around 1990 https://en.wikipedia.org/wiki/Suffix_array)
[ Parent | on HN ]
Re:Binary Decision Diagrams (2010) by psykotic on Wednesday December 09, 2020 @01:10PM (#25361606)
It's an important theoretical result, but the optimized library almost everyone uses (libdivsufsort) is based on an O(n log n) time algorithm; I haven't seen any competitive implementations of the linear-time algorithms.
[ Parent | on HN ]