hdu 5442 Favorite Donut 最大表示法+KMP

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5442

题意：

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

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

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

思路：

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

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

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

  1 #include<iostream>  
  2 #include<string>   
  3 #include<cstring>  
  4 #include<cstdio>  
  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<n; ++i){ 
 16         int j=Next[i]; 
 17         if(j && S[i]!=S[j]) j=Next[j]; 
 18         Next[i+1] = S[i]==S[j]?1+j:0; 
 19     } 
 20 } 
 21  
 22 void find(char* S,char* P,int* Next){ 
 23     getNext(P,Next); 
 24     int n=strlen(S); 
 25     int m=strlen(P); 
 26     int j=0; 
 27     int cnt=0; 
 28     for(int i=0; i<n; ++i){ 
 29         while(j && S[i]!=P[j]) j=Next[j]; 
 30         if(S[i] == P[j]) ++j; 
 31         if(j==m){ 
 32             if(idb[i-m+1] <= bpos1)
 33             {
 34                 bpos1 = idb[i-m+1];
 35     
 36             }
 37         } 
 38     }  
 39 } 
 40 
 41 int GetMax(char *P)  
 42 {  
 43     int len=n;  
 44     int i=0,j=1,k=0;  
 45     while(i<len&&j<len&&k<len)  
 46     {  
 47         int t=P[(i+k)%len]-P[(j+k)%len];  
 48         if(!t) k++;  
 49         else  
 50         {  
 51             if(t>0) j+=k+1;  
 52             else i+=k+1;  
 53             if(i==j) j++;  
 54             k=0;  
 55         }  
 56     }  
 57     return i<j?i:j;  
 58 } 
 59 char s1[20010];
 60 char s2[20010];
 61 int main()
 62 {
 63     int T;
 64     scanf("%d", &T);
 65     while(T--)
 66     {
 67         scanf("%d", &n);
 68         scanf("%s", s1);
 69         s2[0] = s1[0];
 70         for(int i = 1; i < n; i++) s2[i] = s1[n-i];
 71 
 72         idb[0] = 0;
 73         for(int i = 1; i < n; i++) idb[i] = n-i;
 74         for(int i = n; i < 2*n; i++) idb[i] = idb[i-n];
 75 
 76         int apos = GetMax(s1);
 77         int bpos = GetMax(s2);
 78         int apos1 = apos;
 79 
 80         bpos1 = idb[bpos];
 81           
 82 
 83         string a = "", b = "";
 84         for(int i = apos; i < apos+n; i++) a += s1[i%n];
 85         for(int i = bpos; i < bpos+n; i++) b += s2[i%n];
 86 
 87         for(int i = 0; i < n; i++) S[i] = s2[i];
 88         for(int i = n; i < 2*n; i++) S[i] = s2[i-n];
 89         S[2*n] = '';
 90         
 91         char b1[20010];
 92         for(int i = 0; i < n; i++) b1[i] = b[i];
 93         b1[n] = '';
 94         
 95         find(S, b1, Next);
 96 
 97         if(a>b) printf("%d %d
", apos+1, 0);
 98         else if(a < b) printf("%d %d
", bpos1+1, 1);
 99         else
100         {
101             if(apos1 <= bpos1) printf("%d %d
", apos1+1, 0);
102             else printf("%d %d
", bpos1+1, 1);
103         }
104 
105     }
106     return 0;
107 }