Unbordered Words Enumeration

This project provides an implementation for enumerating unbordered words of length up to ( n ),
where each character is drawn from an alphabet of size ( \sigma ).

Each unbordered word is represented in an implicit form, storing its Lyndon conjugate and the corresponding border correlation function.
The implementation supports multiple algorithms and evaluation modes for analyzing efficiency and compression ratio.

This project depends on the following external libraries:

• libdivsufsort
  Used for suffix array and LCP construction in border correlation computations.

• GoogleTest
  Used for unit testing under the tests/ directory.

sudo apt install libdivsufsort-dev
sudo apt install libgtest-dev

We use CMake to build the project:

mkdir build
cd build
cmake ..
make

Follow the steps below to perform different evaluations and experiments related to unbordered word enumeration and border correlation function construction.

1. Enumeration evaluation between the implicit one and the Nielsen's algorithm The log is stored in the file "size_log".

./exp 0 [alphabet_size, max_length]

2. Border correlation function building evaluation The program will randomly generate [repeat] strings of length [length] and evaluate the time consumption (ms) for building the border correlation function by using the KMP and Algorithm~1.

./exp 1 [alphabet_size, length, repeat, len_gap]

3. Compute the border correlation function of a string

./exp 2 [string]

4. (Sampled) enumeration evaluation between the implicit one and the Nielsen's algorithm

./exp 3 [alphabet_size, len, sample_number]