Revolving Digits

港控/mmm° 2021-10-23 11:56 230阅读 0赞

算法：

扩展KMP + KMP找循环节

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<iostream>
    #include<vector>
    #include<string>
    #include<math.h>
    #include<map>
    #include<set>
    #include<algorithm>
    #define MAXN 300010
    using 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;
    }

转载于:https://www.cnblogs.com/tangcong/archive/2012/08/08/2627835.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211023/7576ee9fd5784383be65d8a3298e43eb.png