Cod sursa(job #1801617)

Utilizator robx12lnLinca Robert robx12ln Data 9 noiembrie 2016 13:10:20
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include<fstream>
#include<cstring>
#define DIM 2000005
#define P 73
#define MOD1 100007
#define MOD2 100021
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int hashA1, hashA2, hashB1, hashB2, n, m, nr;
char a[DIM], b[DIM], f[DIM];
int main(){
    fin >> a + 1;
    fin >> b + 1;
    n = strlen( a + 1 );
    m = strlen( b + 1 );
    if( n > m ){
        fout << 0;
        return 0;
    }
    int P1 = 1;
    int P2 = 1;
    for( int i = 1; i <= n; i++ ){
        hashA1 = ( hashA1 * P + a[i] ) % MOD1;
        hashA2 = ( hashA2 * P + a[i] ) % MOD2;
        hashB1 = ( hashB1 * P + b[i] ) % MOD1;
        hashB2 = ( hashB2 * P + b[i] ) % MOD2;
        if( i != 1 ){
            P1 *= P;
            P2 *= P;
            P1 %= MOD1;
            P2 %= MOD2;
        }
    }
    if( hashA1 == hashB1 && hashA2 == hashB2 ){
        f[0] = 1;
        nr++;
    }
    for( int i = n + 1; i <= m; i++ ){
        hashB1 = ( ( hashB1 - (b[i - n] * P1) % MOD1 + MOD1 ) * P + b[i] ) % MOD1;
        hashB2 = ( ( hashB2 - (b[i - n] * P2) % MOD2 + MOD2 ) * P + b[i] ) % MOD2;
        if( hashA1 == hashB1 && hashA2 == hashB2 ){
            f[i - n] = 1;
            nr++;
        }
    }
    fout << nr << "\n";
    int nr = 0;
    for( int i = 0; i <= m && nr < 1000; i++ ){
        if( f[i] == 1 ){
            fout << i << " ";
            nr++;
        }
    }
    return 0;
}