string/duval.cpp


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;
}}}