Cod sursa(job #1268108)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 20 noiembrie 2014 17:03:42
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include<cstdio>

using namespace std;

FILE *fin = fopen( "strmatch.in", "r" ), *fout = fopen( "strmatch.out", "w" );

const int nmax = 2000000;
const int nrsol = 1000;
int n, m, pi[ nmax + 1 ], sol[ nrsol ];
char a[ nmax + 1 ], b[ nmax + 1 ];

void citire() {
    char x;
    x = fgetc( fin );
    n = m = 0;
    while ( (x >= 'A' && x <= 'Z') || (x >= 'a' && x <= 'z') || (x >= '0' && x <= '9') ) {
        a[ ++ m ] = x;
        x = fgetc( fin );
    }
    while ( !(x >= 'A' && x <= 'Z') || (x >= 'a' && x <= 'z') || (x >= '0' && x <= '9') ) {
        x = fgetc( fin );
    }
    do {
        b[ ++ n ] = x;
        x = fgetc( fin );
    } while ( (x >= 'A' && x <= 'Z') || (x >= 'a' && x <= 'z') || (x >= '0' && x <= '9') );
}
int main() {
    int r, ans;
    citire();
    pi[ 1 ] = 0;
    for( int i = 2; i <= m; ++ i ) {
        r = pi[ i - 1 ];
        while ( r != 0 && a[ r + 1 ] != a[ i ] ) {
            r = pi[ r ];
        }
        if ( a[ r + 1 ] == a[ i ] ) {
            pi[ i ] = r + 1;
        } else {
            pi[ i ] = 0;
        }
    }
    ans = 0;
    r = 0;
    for( int i = 1; i <= n; ++ i ) {
        while ( r != 0 && a[ r + 1 ] != b[ i ] ) {
            r = pi[ r ];
        }
        if ( a[ r + 1 ] == b[ i ] ) {
            ++ r;
        }
        if ( r == m ) {
            sol[ ans ++ ] = i - m + 1;
        }
    }

    fprintf( fout, "%d\n", ans );
    for( int i = 0; i < ans && i < nrsol; ++ i ) {
        fprintf( fout, "%d ", sol[ i ] - 1 );
    }
    fclose( fin );
    fclose( fout );
    return 0;
}