Minimal Rotation

Explicación

Mantendremos la rotación lexicográficamente más pequeña a través de su índice de inicio, sea $i$ . Luego, la comparación entre esta y otra rotación, que empieza en el índice $j$ , se hace hallando el primer carácter distinto. Esto se puede hacer rápidamente con búsqueda binaria del valor $d$ tal que $S_{i+d} \neq S_{j+d}$ . Además, se puede usar hashing para comparar los prefijos de las rotaciones.

El algoritmo también se conoce como algoritmo de Booth .

Implementación

Complejidad temporal: $\mathcal{O}(N \cdot \log{N})$

C++


#include <bits/stdc++.h>
 
using namespace std;
 
// BeginCodeSnip{Hashing Template (from the module)}
class HashedString {
  private:
	// cambia M y B si quieres
	static const long long M = 1e9 + 9;
	static const long long B = 9973;
 
	// pow[i] contiene B^i % M
	static vector<long long> pow;
 
	// p_hash[i] es el hash de los primeros i caracteres del string dado
	vector<long long> p_hash;
 
  public:
	HashedString(const string &s) : p_hash(s.size() + 1) {
		while (pow.size() <= s.size()) { pow.push_back((pow.back() * B) % M); }
 
		p_hash[0] = 0;
		for (int i = 0; i < s.size(); i++) {
			p_hash[i + 1] = ((p_hash[i] * B) % M + s[i]) % M;
		}
	}
 
	long long get_hash(int start, int end) {
		long long raw_val = (p_hash[end + 1] - (p_hash[start] * pow[end - start + 1]));
		return (raw_val % M + M) % M;
	}
};
vector<long long> HashedString::pow = {1};
// EndCodeSnip
 
int main() {
	string s;
	cin >> s;
 
	int sz = s.size();  // solo un atajo
	int ans = 0;
 
	// Duplicamos el string para hacerlo circular y evitar trabajar con módulo
	s += s;
	HashedString pref(s);
	for (int i = 0; i < sz; i++) {
		// Búsqueda binaria del primer carácter distinto
		int lo = 0;
		int hi = sz - 1;
		while (lo <= hi) {
			int mid = (lo + hi) / 2;
			// Comprobar si los prefijos coinciden
			if (pref.get_hash(i, i + mid) == pref.get_hash(ans, ans + mid)) {
				lo = mid + 1;
			} else {
				hi = mid - 1;
			}
		}
 
		// Actualizar la respuesta
		if (s[i + lo] < s[ans + lo]) { ans = i; }
	}
 
	cout << s.substr(ans, sz) << endl;
}