duval.cpp File Reference

Implementation of Duval's algorithm. More...

#include <array>
#include <cassert>
#include <cstddef>
#include <deque>
#include <iostream>
#include <string>
#include <vector>

Include dependency graph for duval.cpp:

Go to the source code of this file.

Namespaces
namespace	string
	string manipulation algorithms

Functions
template<typename T >
size_t	string::duval (const T &s)
	Find the lexicographically smallest cyclic shift of a sequence.
static void	test ()
	self test implementation returns void
int	main ()
	main function

Detailed Description

Implementation of Duval's algorithm.

Duval's algorithm is an algorithm to find the lexicographically smallest rotation of a string. It is based on the concept of Lyndon words. Lyndon words are defined as the lexicographically smallest string in a rotation equivalence class. A rotation equivalence class is a set of strings that can be obtained by rotating a string. For example, the rotation equivalence class of "abc" is {"abc", "bca", "cab"}. The lexicographically smallest string in this class is "abc".

Duval's algorithm works by iterating over the string and finding the smallest rotation of the string that is a Lyndon word. This is done by comparing the string with its suffixes and finding the smallest suffix that is lexicographically smaller than the string. This suffix is then added to the result and the process is repeated with the remaining string. The algorithm has a time complexity of O(n) where n is the length of the string.

Note

While Lyndon words are described in the context of strings, Duval's algorithm can be used to find the lexicographically smallest cyclic shift of any sequence of comparable elements.

Author

Amine Ghoussaini

Definition in file duval.cpp.

Function Documentation

main()

int main

(

void

)

main function

Returns

0 on exit

Definition at line 115 of file duval.cpp.

           {
    test();  // run self test implementations
    return 0;
}

test()

static void test ( )

static

self test implementation returns void

Definition at line 77 of file duval.cpp.

                   {
    using namespace string;
 
    // Test 1
    std::string s1 = "abcab";
    assert(duval(s1) == 3);
 
    // Test 2
    std::string s2 = "011100";
    assert(duval(s2) == 4);
 
    // Test 3
    std::vector<int> v = {5, 2, 1, 3, 4};
    assert(duval(v) == 2);
 
    // Test 4
    std::array<int, 5> a = {1, 2, 3, 4, 5};
    assert(duval(a) == 0);
 
    // Test 5
    std::deque<char> d = {'a', 'z', 'c', 'a', 'b'};
    assert(duval(d) == 3);
 
    // Test 6
    std::string s3;
    assert(duval(s3) == 0);
 
    // Test 7
    std::vector<int> v2 = {5, 2, 1, 3, -4};
    assert(duval(v2) == 4);
 
    std::cout << "All tests passed!" << std::endl;
}