一开始没太看懂什么意思，拿笔反复推了一遍才大概知道最大最小表示法是怎么求的，感觉太神奇了...
1 #include <iostream> 2 #include <cstdio> 3 #include <string.h> 4 #pragma warning ( disable : 4996 ) 5 using namespace std; 6 7 inline int Max(int a,int b) { return a>b?a:b; } 8 inline int Min(int a,int b) { return a>b?b:a; } 9 const int inf = 0x3f3f3f3f; 10 const int maxn = 1e6+5; 11 12 char str[maxn]; 13 int nxt[maxn]; 14 int len, plen, minpos, maxpos; 15 16 void getNext() 17 { 18 memset( nxt, 0, sizeof(nxt) ); 19 len = strlen(str); 20 21 int k = -1, j = 0; 22 nxt[j] = -1; 23 24 while ( j < len ) 25 { 26 if ( k==-1 || str[j]==str[k] ) 27 { 28 k++; j++; 29 nxt[j] = k; 30 } 31 else 32 k = nxt[k]; 33 } 34 plen = nxt[len]; 35 } 36 37 void getMin() 38 { 39 int tmp, i = 0, j = 1, k = 0; 40 while ( i<len && j <len && k <len ) 41 { 42 tmp = str[(i+k)%len]-str[(j+k)%len]; 43 if(!tmp) k++; 44 else 45 { 46 if(tmp>0) i += k+1; 47 else j += k+1; 48 if( i == j ) j++; 49 k = 0; 50 } 51 } 52 minpos = i<j?i+1:j+1; 53 } 54 55 void getMax() 56 { 57 int tmp, i = 0, j = 1, k = 0; 58 while ( i<len && j<len && k<len ) 59 { 60 tmp = str[(i+k)%len]-str[(j+k)%len]; 61 if(!tmp) k++; 62 else 63 { 64 if(tmp<0) i += k+1; 65 else j += k+1; 66 if( i == j ) j++; 67 k = 0; 68 } 69 } 70 maxpos = i<j?i+1:j+1; 71 } 72 73 int main() 74 { 75 while ( ~scanf("%s", str) ) 76 { 77 getNext(); 78 getMin(); 79 getMax(); 80 81 int tmp = (len%(len-plen)==0)?(len/(len-plen)):1; 82 printf( "%d %d %d %d ", minpos, tmp, maxpos, tmp ); 83 } 84 return 0; 85 }