题目链接：

题意：

有一个由小写字母组成的字符串(长度为n)，首尾相接，求顺时针转和逆时针转的情况下,长度为n的最大字典序的字符串的首位的位置。

如果顺时针和逆时针求得的字符串相同，则选择开始位置较前的，如果开始位置也相同，则选择顺时针的。

如abcd，那么顺时针可以是abcd,bcda,cdab,dabc.逆时针可以是adcb,dcba,cbad,badc.

 

思路：

顺时针的情况下，直接求最大字典序的位置。逆时针的情况下，由于求最大字典序的串与原串对应位置的编号发生变化，

所以求得位置后，得到字典序最大的字符串，再用kmp找出该字符串在母串中出现的所有位置，取最靠前的位置。

然后把顺时针和逆时针的情况进行比较。

1 #include
     
          2 #include
      
            3 #include
       
            4 #include
        
             5 using namespace std;    6 int n;  7 char S[20010*2];  8 int Next[1000005];  9 char P[20010*2]; 10 int idb[20010*2]; 11 int bpos1; 12 void getNext(char* S,int* Next){  13     int n=strlen(S);  14     Next[0]=Next[1]=0;  15     for(int i=1; i
         
          0) j+=k+1;   52             else i+=k+1;   53             if(i==j) j++;   54             k=0;   55         }   56     }   57     return i
          
           b) printf("%d %d\n", apos+1, 0); 98 else if(a < b) printf("%d %d\n", bpos1+1, 1); 99 else100 {101 if(apos1 <= bpos1) printf("%d %d\n", apos1+1, 0);102 else printf("%d %d\n", bpos1+1, 1);103 }104 105 }106 return 0;107 }