Minimum Rotation

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Returns the 0-based index k such that rotation R_k(s) is lexicographically minimum.
5
// Implements Booth's algorithm using a KMP-like failure function over t = s + s.
6
int booth_min_rotation_index(const string &s) {
7
    int n = (int)s.size();
8
    if (n == 0) return 0; // define empty string's min rotation index as 0
9
    string t = s + s;               // length 2n
10
    int m = (int)t.size();          // 2n
11
    vector<int> f(m, -1);           // failure function relative to current best start
12
    int k = 0;                      // best rotation start seen so far in t
13
14
    for (int j = 1; j < m; ++j) {
15
        // i is length of current border relative to k
16
        int i = f[j - k - 1];
17
        // Fall back using failure links while mismatch persists
18
        while (i != -1 && t[j] != t[k + i + 1]) {
19
            if (t[j] < t[k + i + 1]) {
20
                // Found a smaller character; new best start is j - i - 1
21
                k = j - i - 1;
22
            }
23
            i = f[i];
24
        }
25
        // Now either i == -1 or t[j] == t[k + i + 1]
26
        if (t[j] != t[k + i + 1]) {
27
            // No extension possible; border length becomes -1
28
            if (t[j] < t[k + i + 1]) {
29
                // New better rotation starts at position j
30
                k = j;
31
            }
32
            f[j - k] = -1;
33
        } else {
34
            // Extend border
35
            f[j - k] = i + 1;
36
        }
37
        // Optimization: once k reaches n, the answer modulo n is fixed
38
        if (k >= n) break;
39
    }
40
    return k % n;
41
}
42
43
// Build the minimum rotation string using the index.
44
string booth_min_rotation(const string &s) {
45
    if (s.empty()) return s;
46
    int k = booth_min_rotation_index(s);
47
    return s.substr(k) + s.substr(0, k);
48
}
49
50
int main() {
51
    ios::sync_with_stdio(false);
52
    cin.tie(nullptr);
53
54
    vector<string> tests = {
55
        "bca",        // -> abc
56
        "aaaa",       // -> aaaa (many equal rotations)
57
        "caba",       // -> abac
58
        "ababab",     // -> ababab (many equal rotations)
59
        "dbcaacb"     // random
60
    };
61
62
    for (const auto &s : tests) {
63
        int idx = booth_min_rotation_index(s);
64
        string rot = booth_min_rotation(s);
65
        cout << "s = " << s << ", index = " << idx << ", min rotation = " << rot << "\n";
66
    }
67
    return 0;
68
}
69

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Duval's algorithm to factorize a string into Lyndon words.
5
// Returns half-open intervals [l, r) of each Lyndon factor in order.
6
vector<pair<int,int>> lyndon_factorization(const string &s) {
7
    int n = (int)s.size();
8
    vector<pair<int,int>> res;
9
    int i = 0;
10
    while (i < n) {
11
        int j = i + 1, k = i;
12
        while (j < n && s[k] <= s[j]) {
13
            if (s[k] < s[j]) k = i; // reset k when strictly smaller seen
14
            else ++k;                // advance k when equal
15
            ++j;
16
        }
17
        // Now s[i..k] is the Lyndon word, and it repeats (j - k) times
18
        while (i <= k) {
19
            res.emplace_back(i, i + (j - k));
20
            i += (j - k);
21
        }
22
    }
23
    return res;
24
}
25
26
// Linear-time minimum rotation using Duval's idea (often presented as Booth's other variant).
27
// Returns the 0-based index of the minimum rotation.
28
int duval_min_rotation_index(const string &s) {
29
    int n = (int)s.size();
30
    if (n == 0) return 0;
31
    string t = s + s; // length 2n
32
    int i = 0, ans = 0;
33
    while (i < n) { // only need starts < n
34
        ans = i;
35
        int j = i + 1, k = i;
36
        // Find the first position where t[k] < t[j] or t[k] > t[j]
37
        while (j < i + n && t[k] <= t[j]) {
38
            if (t[k] < t[j]) k = i; // reset k on strictly smaller
39
            else ++k;               // advance k on equal
40
            ++j;
41
        }
42
        // Skip over the block of size (j - k)
43
        while (i <= k) i += (j - k);
44
    }
45
    return ans;
46
}
47
48
string duval_min_rotation(const string &s) {
49
    if (s.empty()) return s;
50
    int idx = duval_min_rotation_index(s);
51
    return s.substr(idx) + s.substr(0, idx);
52
}
53
54
int main() {
55
    ios::sync_with_stdio(false);
56
    cin.tie(nullptr);
57
58
    vector<string> tests = {
59
        "bca", "aaaa", "caba", "ababab", "zzzxyzz"
60
    };
61
62
    for (const auto &s : tests) {
63
        int idx = duval_min_rotation_index(s);
64
        auto factors = lyndon_factorization(s + s);
65
        cout << "s = " << s << "\n";
66
        cout << "  min-rotation index (Duval-based) = " << idx << ", string = "
67
             << s.substr(idx) + s.substr(0, idx) << "\n";
68
        cout << "  Lyndon factors of s+s (as [l,r)):\n    ";
69
        for (auto [l, r] : factors) {
70
            cout << "[" << l << "," << r << ") '" << (s + s).substr(l, r - l) << "'  ";
71
        }
72
        cout << "\n\n";
73
    }
74
    return 0;
75
}
76

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Booth: linear-time minimum rotation index
5
int booth_min_rotation_index(const string &s) {
6
    int n = (int)s.size();
7
    if (n == 0) return 0;
8
    string t = s + s;
9
    int m = (int)t.size();
10
    vector<int> f(m, -1);
11
    int k = 0;
12
    for (int j = 1; j < m; ++j) {
13
        int i = f[j - k - 1];
14
        while (i != -1 && t[j] != t[k + i + 1]) {
15
            if (t[j] < t[k + i + 1]) k = j - i - 1;
16
            i = f[i];
17
        }
18
        if (t[j] != t[k + i + 1]) {
19
            if (t[j] < t[k + i + 1]) k = j;
20
            f[j - k] = -1;
21
        } else {
22
            f[j - k] = i + 1;
23
        }
24
        if (k >= n) break;
25
    }
26
    return k % n;
27
}
28
29
// Returns the canonical (minimum rotation) representative of s
30
string canonical_necklace(const string &s) {
31
    if (s.empty()) return s;
32
    int k = booth_min_rotation_index(s);
33
    return s.substr(k) + s.substr(0, k);
34
}
35
36
// Compares two cyclic strings A and B lexicographically by their canonical representatives
37
int compare_cyclic(const string &A, const string &B) {
38
    string a = canonical_necklace(A);
39
    string b = canonical_necklace(B);
40
    if (a < b) return -1;
41
    if (a > b) return 1;
42
    return 0;
43
}
44
45
int main() {
46
    ios::sync_with_stdio(false);
47
    cin.tie(nullptr);
48
49
    // Example: deduplicate strings up to rotation
50
    vector<string> S = {"bca", "abc", "cab", "aaaa", "aa", "a", "xyzz", "zzxy", "zzyx"};
51
    unordered_set<string> uniq;
52
    for (auto &s : S) uniq.insert(canonical_necklace(s));
53
54
    cout << "Unique necklaces (canonical forms):\n";
55
    for (const auto &x : uniq) cout << x << "\n";
56
57
    // Compare two cyclic strings
58
    string A = "caba", B = "abac"; // these are rotations of each other
59
    int cmp = compare_cyclic(A, B);
60
    cout << "Compare cyclic A vs B: ";
61
    if (cmp < 0) cout << "A < B\n";
62
    else if (cmp > 0) cout << "A > B\n";
63
    else cout << "A == B (as necklaces)\n";
64
65
    return 0;
66
}
67