Cod sursă (job #617607)

#include <stdio.h>
#include <cstring>

static inline int min( const int& a, const int& b ) {
    return ( a <= b ? a : b );
}

#define MAX 500000

int z[ MAX + 1 ];
char s[ MAX + 1 ];
int n, m;

int Z_algorithm( int z[] ) {
    z[ 0 ] = 0;
    int right = 0, left = 0, poz = -1;
    for( int i = 1; i < n; i++ ) {
        if( i <= right )
            z[ i ] = min( z[ i - left ], right - i + 1 );
        while( i + z[ i ] < n && s[ i + z[ i ] ] == s[ z[ i ] ] )
            ++z[ i ];

        if( i + z[ i ] - 1 > right ) {
            right = i + z[ i ] - 1;
            left = i;
        }

        if( poz == -1 && i + z[ i ] == n )
            poz = i;
    }

    return ( poz == -1 ? n : poz );
}

int main()
{
    FILE *fin = fopen( "bart.in", "r" );
    fscanf( fin, "%s", s );

    n = strlen( s );
    int poz = Z_algorithm( z );

    s[ poz ] = '\0';
    FILE *fout = fopen( "bart.out", "w" );
    fprintf( fout, "%s\n", s );
    fclose( fout );
    return 0;
}