1 files changed, 21 insertions, 0 deletions
diff --git a/content/string/duval.cpp b/content/string/duval.cpp
new file mode 100644
index 0000000..bf36cce
--- /dev/null
+++ b/content/string/duval.cpp
@@ -0,0 +1,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;
+}}}