Revolving Digits-蒲公英云

Revolving Digits

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

算法：

扩展KMP + KMP找循环节

#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;
}