updated tcr

1 files changed, 21 insertions, 0 deletions

diff --git a/string/duval.cpp b/string/duval.cpp
new file mode 100644
index 0000000..6d80e95
--- /dev/null
+++ b/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 e : parts) {
+		if (e.first < sz(s) && e.second >= sz(s)) {
+			return e.first;
+}}}