Cod sursa(job #1081629)

Utilizator Athena99Anghel Anca Athena99 Data 13 ianuarie 2014 19:41:57
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <cassert>
#include <cstdio>
#include <cstring>

using namespace std;

const int nmax=2000000;
const int solmax= 1000;

int p[nmax+1], sol[solmax+1];
char a[nmax+1], b[nmax+1];
 
void prefix( int n ) {
    int k= 0;
    for ( int i= 2; i<=n; ++i ) {
        while ( k>0 && a[k+1]!=a[i] ) {
            k= p[k];
        }
        if (a[k+1]==a[i]) {
            ++k;
        }
 
        p[i]=k;
    }
}

int main(  ) {
    assert( freopen( "strmatch.in", "r", stdin ) );
    assert( freopen( "strmatch.out", "w", stdout) );
    
    assert(scanf("%s%s",a+1,b+1));
    int n=strlen(a+1), m=strlen(b+1);
 
    prefix(n);
    int k= 0, soln= 0;
    for ( int i= 1; i<=m; ++i ) {
        while ( k>0 && a[k+1]!=b[i] ) {
            k= p[k];
        }
        if ( a[k+1]==b[i] ) {
            ++k;
        }

        if ( k==n ) {
            ++soln;
            if ( soln<=solmax ) {
                sol[soln]= i-n;
            }
        }
    }

    assert( printf( "%d\n", soln ) );
    for ( int i= 1; i<=soln && i<=solmax; ++i ) {
        assert( printf( "%d ", sol[i] ) );
    }
    assert( printf( "\n" ) );
 
    return 0;
}