This repo provides an efficient implementation of the Ukkonen85 algorithm, which is sometimes also known as Myers' O(ND) algorithm or the Landau-Vishkin algorithm. Please see the notes here for a historical background.

There are two implementations. u85-basic.c gives a basic implementation. It is more complex but can be faster than the original algorithm when input sequences are distinct in length. u85-fast.c is an optimized version. It is comparable to edlib in speed on a few examples.