复杂度 O(n)
最小表示法及其证明
#include <bits/stdc++.h> using namespace std; const int MAXN = 1E6; char s[MAXN]; int minstr(const char s[], int len, int op = 0)//op=0 := 最小表示, op=1 := 最大表示 { int i=0, j=1, k; while(i<len && j<len) { k = 0; while(k<len && s[(i+k)%len]==s[(j+k)%len]) ++k; if(k == len) break; if((s[(i+k)%len] > s[(j+k)%len])^op) i+=k+1; else j+=k+1; if(i==j) ++j; } return min(i, j); } int main() { while(cin >> s) { int len = strlen(s); int p = minstr(s, len, 1); for(int i=0; i<len; ++i) cout << s[(p+i)%len]; cout << endl; } return 0; }