Cod sursa(job #2592485)

Utilizator OnofreiTudorOnofrei Tudor OnofreiTudor Data 1 aprilie 2020 18:55:12
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <cstring>

#define PRIM1 699967
#define PRIM2 699953

using namespace std;

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

char N[2000005], M[2000005];
int i, n, m, valori, p[1005];
long long putere1, putere2, hash11, hash12, hash21, hash22, val;

bool prim(int x){
    int d;
    for(d = 2; d * d <= x && x % d != 0; d++);
    return d*d > x ? 1 : 0;
}

int main()
{

    fin >> M >> N;
    putere1 = putere2 = 1;
    n = strlen(N);
    m = strlen(M);
    hash11 = hash12 = 0;
    for(i = 0; i<=m-1; i++){
        hash11 = (hash11 * 29 + M[i]) % PRIM1;
        hash12 = (hash12 * 29 + M[i]) % PRIM2;
        if(i != 0){
            putere1 = (putere1 * 29) % PRIM1;
            putere2 = (putere2 * 29) % PRIM2;
        }
    }
    hash21 = hash22 = 0;
    for(i = 0; i<=m-1; i++){
        hash21 = (hash21 * 29 + N[i]) % PRIM1;
        hash22 = (hash22 * 29 + N[i]) % PRIM2;
    }
    if(hash11 == hash21 && hash12 == hash22){
        valori++;
        p[valori] = 0;
    }
    for(i = 1; i<=n-m && valori <= 1000; i++){
        hash21 = ((hash21 - (N[i-1]*putere1) % PRIM1 + PRIM1) * 29 + N[i+m-1]) % PRIM1;
        hash22 = ((hash22 - (N[i-1]*putere2) % PRIM2 + PRIM2) * 29 + N[i+m-1]) % PRIM2;
        if(hash11 == hash21 && hash12 == hash22){
            valori++;
            p[valori] = i;
        }
    }
    fout << valori << '\n';
    for(i = 1; i<=valori; i++){
        fout << p[i] << ' ';
    }

    return 0;
}