Cod sursa(job #1582649)

Utilizator ovidiuz98Zamfir Ovidiu ovidiuz98 Data 28 ianuarie 2016 11:00:26
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#define DIM 2000001
#include <cstring>

#define P 73
#define MOD1 100007
#define MOD2 100021

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char A[DIM],B[DIM];

int NA,NB;
int match[DIM], hash1, hash2, P1, P2, hashA1, hashA2;

int main(){

    fin >> A >> B;

    NA = strlen(A);
    NB = strlen(B);

    P1 = P2 = 1;
    hashA1 = hashA2 = 0;

    for(int i=0;i<NA;i++){
        hashA1 = (hashA1 * P + A[i]) % MOD1;
        hashA2 = (hashA2 * P + A[i]) % MOD2;
        if(i!=0){
            P1 = (P1 * P) % MOD1;
            P2 = (P2 * P) % MOD2;
        }
    }

    if(NA > NB){
        fout << "0\n";
        return 0;
    }

    hash1 = hash2 = 0;

    for(int i=0;i<NA;i++){
        hash1 = (hash1*P+B[i])%MOD1;
        hash2 = (hash2*P+B[i])%MOD2;
    }

    int Nr = 0;
    if(hash1==hashA1 && hash2==hashA2)
        Nr++,match[0]=1;

    for(int i=NA;i<NB;i++){
        hash1 = ((hash1 - (B[i-NA] * P1)%MOD1 + MOD1) * P +B[i]) % MOD1;
        hash2 = ((hash2 - (B[i-NA] * P2)%MOD2 + MOD2) * P +B[i]) % MOD2;

        if(hash1==hashA1 && hash2==hashA2)
            match[i - NA + 1]=1, Nr++;
    }

    fout << Nr << "\n";
    Nr=0;
    for(int i=0;i<NB && Nr<1000;i++)
        if(match[i]){
            Nr++;
            fout << i << " ";
        }
    fout << "\n";

}