duval.cpp

Go to the documentation of this file.

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

namespace string {
template <typename T>
size_t duval(const T& s) {
    size_t n = s.size();
    size_t i = 0, ans = 0;
    while (i < n) {
        ans = i;
        size_t j = i + 1, k = i;
        while (j < (n + n) && s[j % n] >= s[k % n]) {
            if (s[k % n] < s[j % n]) {
                k = i;
            } else {
                k++;
            }
            j++;
        }
        while (i <= k) {
            i += j - k;
        }
    }
    return ans;
    // returns 0-indexed position of the least cyclic shift
}
 
}  // namespace string

static void test() {
    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;
}

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