This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub AlexanderNekrasov/Youthful-Passion-Fruit-teambook
/** * Author: Iurii Pustovalov * Date: 2022-11-08 * Description: Calculates min-cyclic-shift of s, Duval decomposition * Time: O(n) */ string minshift(string s) { int i = 0, ans = 0; s += s; int n = s.size(); while (i < n / 2) { ans = i; int j = i + 1, k = i; while (j < n && s[k] <= s[j]) { if (s[k] < s[j]) k = i; else ++k; ++j; } while (i <= k) { i += j - k; } } return s.substr(ans, n / 2); }
#line 1 "strings/MinShift.cpp" /** * Author: Iurii Pustovalov * Date: 2022-11-08 * Description: Calculates min-cyclic-shift of s, Duval decomposition * Time: O(n) */ string minshift(string s) { int i = 0, ans = 0; s += s; int n = s.size(); while (i < n / 2) { ans = i; int j = i + 1, k = i; while (j < n && s[k] <= s[j]) { if (s[k] < s[j]) k = i; else ++k; ++j; } while (i <= k) { i += j - k; } } return s.substr(ans, n / 2); }