Cod sursa(job #1691387)

Utilizator robx12lnLinca Robert robx12ln Data 18 aprilie 2016 10:34:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include<fstream>
#include<cstring>
#define P 73
#define MOD1 100023
#define MOD2 100071
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int NA, NB, HashA1, HashA2, HashB1, HashB2, P1, P2, nr;
char A[2000005], B[2000005], f[2000005];
int main(){
    fin >> A;
    fin >> B;
    NA = strlen( A );
    NB = strlen( B );
    if( NA > NB ){
        fout << 0;
        return 0;
    }
    P1 = P2 = 1;
    for( int i = 0; i < NA; 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 != 0 ){
            P1 = ( P1 * P ) % MOD1;
            P2 = ( P2 * P ) % MOD2;
        }
    }
    nr = 0;
    if( HashA1 == HashB1 && HashA2 == HashB2 ){
        f[0] = 1;
        nr++;
    }
    for( int i = NA; i < NB; i++ ){
        HashB1 = ( ( HashB1 - ( P1 * B[i - NA] ) % MOD1 + MOD1 ) * P + B[i] ) % MOD1;
        HashB2 = ( ( HashB2 - ( P2 * B[i - NA] ) % MOD2 + MOD2 ) * P + B[i] ) % MOD2;
        if( HashA1 == HashB1 && HashA2 == HashB2 ){
            f[i - NA + 1] = 1;
            nr++;
        }
    }
    fout << nr << "\n";
    nr = 0;
    for( int i = 0; i < NB && nr < 1000; i++ ){
        if( f[i] == 1 ){
            fout << i << " ";
            nr++;
        }
    }
    return 0;
}