blob: bf36cce70151d79df041224714798c9d8670470c (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
vector<pair<int, int>> duval(const string& s) {
vector<pair<int, int>> res;
for (int i = 0; i < sz(s);) {
int j = i + 1, k = i;
for (; j < sz(s) && s[k] <= s[j]; j++) {
if (s[k] < s[j]) k = i;
else k++;
}
while (i <= k) {
res.push_back({i, i + j - k});
i += j - k;
}}
return res;
}
int minrotation(const string& s) {
auto parts = duval(s+s);
for (auto [l, r] : parts) {
if (l < sz(s) && r >= sz(s)) {
return l;
}}}
|
