MinRotation

Finds the lexicographically smallest rotation of a string.

Time: O(N) 8 lines Stress-tested

Usage: rotate(v.begin(), v.begin()+minRotation(v), v.end());

content/strings/MinRotation.h — Stjepan Glavina, source: https://github.com/stjepang/snippets/blob/master/min_rotation.cpp

int minRotation(string s) {
	int a=0, N=sz(s); s += s;
	rep(b,0,N) rep(k,0,N) {
		if (a+k == b || s[a+k] < s[b+k]) {b += max(0, k-1); break;}
		if (s[a+k] > s[b+k]) { a = b; break; }
	}
	return a;
}