字符串的最小表示法

O ( n ) 的算法

int TheMinimumRepresentation ( char* s )  {
    int n = strlen ( s ) ;
    int i ( 0), j ( 1 ), k ( 0 ) ;
    while ( i < n && j < n && k < n )  {
        int delta = s [( i + k ) % n] - s[( j + k ) % n] ;
        if ( ! delta ) ++ k ;
        else  {
            if ( delta > 0 ) i += k + 1 ; 
            else j += k + 1 ;
            if ( i == j ) ++ j ;
            k = 0 ;
        }
    }
    return i < j ? i : j ;
}

例： BZOJ1398， 裸最小表示法。

# include <bits/stdc++.h>

inline int TheMinimumRepresentation ( char* s, int n )  {
// int n = strlen ( s ) ;
    int i ( 0), j ( 1 ), k ( 0 ) ;
    while ( i < n && j < n && k < n )  {
        int delta = s [( i + k ) % n] - s[( j + k ) % n] ;
        if ( ! delta ) ++ k ;
        else  {
            if ( delta > 0 ) i += k + 1 ; 
            else j += k + 1 ;
            if ( i == j ) ++ j ;
            k = 0 ;
        }
    }
    return i < j ? i : j ;
}

const int N = 1234567 ;

char buf [N << 1], *ip ;
char s1 [N], s2 [N] ;
char ss1 [N], ss2 [N] ;

int main ( )  {
    fread ( ip = buf, 1, N << 1, stdin ) ;
    int len ( 0 ) ;
    while ( *ip > 10 )  s1 [len ++] = *ip ++ ;
    while ( *ip == 10 )  ++ ip ;
    len = 0 ;
    while ( *ip > 10 )  s2 [len ++] = *ip ++ ;
    int st1 = TheMinimumRepresentation ( s1, len ), st2 = TheMinimumRepresentation ( s2, len ) ;
    int cnt ( 0 ) ;
    for ( register int i = st1 ; i < len ; ++ i )  ss1 [cnt ++] = s1 [i] ;
    for ( register int i = 0 ; i < st1 ; ++ i )  ss1 [cnt ++] = s1 [i] ;
    cnt = 0 ;
    for ( register int i = st2 ; i < len ; ++ i )  ss2 [cnt ++] = s2 [i] ;
    for ( register int i = 0 ; i < st2 ; ++ i )  ss2 [cnt ++] = s2 [i] ;
    if ( strcmp ( ss1, ss2 ) != 0 )  {
        puts ( "No" ) ;
    }  else  {
        puts ( "Yes" ) ;
        puts ( ss1 ) ;
    }
    return 0 ;
}