用于Lyndon分解和最小旋转计算的Duval算法

我们提供C++、Rust和Python中Duval算法的Lyndon分解和最小旋转计算实现。

我们的Lyndon分解代码基于此实现。

我们的最小旋转计算代码是自定义的且高度优化（针对C++和Rust版本）。

使用方法

纯Python

只需使用以下代码片段（来自duval_pure.py）

def min_rotation(s):
    N = len(s)
    s += s
    a = b = 0
    while b < N:
        for i in range(N - a):
            sai = s[a + i]
            sbi = s[b + i]
            if sai < sbi or a + i == b:
                if i:
                    b += i - 1
                break
            if sai > sbi:
                a = b
                break
        b += 1
    return a

从Python调用C++

需要pybind11 (pip install pybind11)。

使用pip install ./duval-py安装

from duval import duval, min_rotation

s = "abracadabra"
print(duval(s))
print(min_rotation(s))

C++

只需包含duval-cpp/duval.hpp。

#include <iostream>
#include <string>
#include "duval.hpp"

int main()
{
    std::string s = "abracadabra";
    for (auto &factor : duval(s))
        std::cout << factor << std::endl;
    std::cout << min_rotation(s) << std::endl;
}

Rust

代码在duval-rs中提供。

测试

我们为Python、C++和Rust版本提供简单的测试。

C++

cdduval-cpp && g++ --std=c++11 -O3test.cpp -otest && ./test && cd ..

我们对C++版本进行了扩展测试，使用随机字符串与一个非常原始的实现进行对比。随机字符串使用固定的种子生成，以确保可重复性。

我们还展示了性能。在我们的笔记本电脑上，对长度为10000的10000个字符串（一半随机一半随机）的min_rotation计算需要0.2秒。

Python

python duval-py/test.py

我们测试了纯Python和C++版本，并比较了它们的性能。Python版本比C++版本慢约150倍。

Rust

cargotest --manifest-path=duval-rs/Cargo.toml --release ----nocapture

Rust版本的性能与C++版本大致相同。