Revolving Digits-白红宇

Revolving Digits

阅读量：4325 次

发布时间：2019-06-06

本文共 1518 字，大约阅读时间需要 5 分钟。

算法：

扩展KMP + KMP找循环节

View Code

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #define MAXN 300010using namespace std;char S[MAXN], T[MAXN];int next[MAXN];int extend[MAXN];int knext[MAXN];int L, E, G, len;void get_next( ){ int i = 0, j = 1, k = 1; len = strlen(T); next[0] = len; while( T[i] == T[i + k] ) i++; next[1] = i; for( int i = 2; i < len; i++) { if( i + next[i - k] < k + next[k] ) next[i] = next[i - k]; else { j = max(0, k + next[k] - i); while( T[j] == T[i + j] ) j++; next[k = i] = j; } } }//用KMP判断是否有循环节 void KMP( ){ int i = 0, j = -1; knext[0] = -1; while( i <= len ) { if( j == -1 || T[i] == T[j] ) { ++i, ++j; knext[i] = j; } else j = knext[j]; } // printf("len = %d knext[len] = %d\n",len,knext[len]); if( len - knext[len] != 0 && len - knext[len] != len && len % (len - knext[len]) == 0 ) { len = len - 1 - knext[len] + 1; //循环节长度 }}void solve( ){ int lenx = strlen(T); for( int i = 0; i < len; i++) { if( next[i] >= lenx ) E++; else if( S[next[i] + i] > S[next[i]] ) { G++; } else L++; } }int main( ){ int N, abc = 1; scanf("%d",&N); while( N-- ) { scanf("%s",T); strcpy(S,T); strcat(S,T); memset(next,0,sizeof(next)); memset(knext,0,sizeof(knext)); get_next( ); L = E = G = 0; KMP( ); solve( ); printf("Case %d: %d %d %d\n",abc++,L,E,G); } return 0;}