Duval algorithm for Lyndon factorization and smallest rotation computation
We provide implementation of Duval algorithm for Lyndon factorization and smallest rotation computation in C++, Rust and Python.
Our code for the Lyndon factorization is based on this implementation.
Our code for the smallest rotation computation is custom and highly optimized (for the C++ and Rust versions).
Usage
Pure Python
Just use the following code snippet (from duval_pure.py
)
=
+=
= = 0
=
=
+= - 1
break
=
break
+= 1
return
Call C++ from Python
Requires pybind11 (pip install pybind11
).
Install with pip install ./duval-py
=
C++
Simply include duval-cpp/duval.hpp
.
int
Rust
Code is provided in duval-rs
.
Testing
We provide simple tests for the Python, C++ and Rust versions.
C++
cd duval-cpp && g++ --std=c++11 -O3 test.cpp -o test && ./test && cd ..
We do extended testing for the C++ version with random strings against a very naive implementation. The random strings are generated with fixed seeds to ensure reproducibility.
We also display the performance. On our laptop, computing min_rotation
for 10000 strings (half random and half random) of length 10000 takes 0.2s.
Python
python duval-py/test.py
We test both the pure Python and the C++ version and compare their performance. The Python version is about 150x slower than the C++ version.
Rust
cargo test --manifest-path=duval-rs/Cargo.toml --release -- --nocapture
The Rust version has about the same performance as the C++ version.