hdu 3374

 1 #include <iostream>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <cstdio>
 5 const int N = 1000000 + 11;
 6 using namespace std;
 7 char ss[N],s[N<<1];
 8 int cs,n,a[N<<1],nxt[N];
 9 
10 void pre()
11 {
12     nxt[1] = 0; int k = 0;
13     for(int i = 2; i <= n; ++i)
14     {
15         while(k > 0 && a[i] != a[k+1]) k = nxt[k];
16         if(a[i] == a[k+1]) ++k;
17         nxt[i] = k;
18     }
19 }
20 
21 void Init()
22 {
23     n = strlen(ss);
24     strcpy(s,ss);
25     strcat(s,ss);
26     for(int i = 0; i < ( n << 1 ); ++i) a[i+1] = s[i]; 
27     pre();
28 }
29 
30 int minx()
31 {
32     
33     int i = 1,j = 2,k = 0;
34     while(i <= n && j <= n  && k < n)
35     {
36         if(a[i+k] == a[j+k] ) ++k;
37         else if(a[i+k] < a[j+k]) j = j + k + 1, k = 0;
38         else i = i + k + 1, k = 0;
39         if( i == j ) ++j;
40     }
41     return i;
42 }
43  
44 void Solve()
45 {
46     cs = n - nxt[n]; 
47     if(n % cs == 0) cs = n/cs; else cs = 1; n = n/cs;
48     printf("%d %d ",minx(),cs);
49     for(int i = 1;i <= ( n << 1 ); ++i) a[i] = 0-a[i];
50     printf("%d %d",minx(),cs);
51 }
52 
53 
54 int main()
55 {
56     while(~scanf("%s",ss))
57     {
58         Init();
59         Solve();
60         puts("");
61     }
62     return 0;
63 }