Cod sursa(job #335315)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 29 iulie 2009 15:01:33
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <algorithm>
using namespace std;

#define DIM 2000005
#define MAX 1000

int n, m, rez, pi[ DIM ], sol[ DIM ];
char a[ DIM ], b[ DIM ];

void calc_pi() {

    int i, k;

    k = 0;
    for( i = 2; i <= n; ++ i ) {

        while( a[ k + 1 ] != a[ i ] && k )
            k = pi[ k ];
        if( a[ k + 1 ] == a[ i ] )
            ++ k;
        pi[ i ] = k;
    }
}

void kmp() {

    int i, k;

    k = 0;
    for( i = 1; i <= m; ++ i ) {

        while( a[ k + 1 ] != b[ i ] && k )
            k = pi[ k ];
        if( a[ k + 1 ] == b[ i ] )
            ++ k;
        if( k == n ) {

            k = pi[ n ];
            ++ rez;
            if( rez <= MAX )
                sol[ rez ] = i - n;
        }
    }
}

void solve() {

    int i;

    gets( a + 1 );
    n = strlen( a + 1 );
    gets( b + 1 );
    m = strlen( b + 1 );
    calc_pi();
    kmp();
    printf( "%d\n", rez );
    for( i = 1; i <= min( rez, MAX ); ++ i )
        printf( "%d ", sol[ i ] );
}

int main() {

    freopen( "strmatch.in", "r", stdin );
    freopen( "strmatch.out", "w", stdout );

    solve();

    return 0;
}