Cod sursa(job #3369219)

Utilizator MateiDiaconuDiaconu Matei Stefan MateiDiaconu Data 17 octombrie 2026 21:03:56
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.47 kb
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

#define MAXS 2000000
#define MOD1 (1 << 15)
#define MOD2 (1 << 17)
#define BASE1 273
#define BASE2 335

char a[MAXS + 2], b[MAXS + 2];
int a_length, b_length;

int positions[MAXS];
int cnt;

int get_hash(char s[], int len, int base, int mod){
    int i, strhash;

    strhash = 0;
    for(i = 0; i < len; i++){
        strhash = (strhash * base + s[i]) % mod;
    }

    return strhash;
}

int add_to_hash(char ch, int strhash, int base, int mod){
    strhash = (strhash * base + ch) % mod;

    return strhash;
}

int remove_from_hash(char ch, int strhash, int power, int mod){
    strhash = (strhash - power * ch) % mod;
    if(strhash < 0){
        strhash += mod;
    }

    return strhash;
}

int pow_mod(int a, int b, int mod){
    int rez;
    rez = 1;
    while(b > 0){
        if(b % 2 == 1){
            rez = (1LL * rez * a) % mod;
        }
        a = (1LL * a * a) % mod;
        b /= 2;
    }

    return rez;
}

void eliminate_new_line(){
    if(a[a_length - 1] == '\n'){
        a[a_length - 1] = '\0';
        a_length--;
    }
    if(b[b_length - 1] == '\n'){
        b[b_length - 1] = '\0';
        b_length--;
    }
}

int main(){
    FILE *fin, *fout;
    fin = fopen("strmatch.in", "r");
    fout = fopen("strmatch.out", "w");
    
    int pow1, pow2, i, a_hash1, a_hash2, b_hash1, b_hash2;

    fgets(a, MAXS + 2, fin);
    fgets(b, MAXS + 2, fin);

    a_length = strlen(a);
    b_length = strlen(b);

    eliminate_new_line();

    pow1 = pow_mod(BASE1, a_length - 1, MOD1);
    pow2 = pow_mod(BASE2, a_length - 1, MOD2);

    a_hash1 = get_hash(a, a_length, BASE1, MOD1);
    a_hash2 = get_hash(a, a_length, BASE2, MOD2);

    b_hash1 = get_hash(b, a_length, BASE1, MOD1);
    b_hash2 = get_hash(b, a_length, BASE2, MOD2);

    if(a_hash1 == b_hash1 && a_hash2 == b_hash2){
        positions[cnt++] = 0;
    }

    for(i = a_length; i < b_length; i++){
        b_hash1 = remove_from_hash(b[i - a_length], b_hash1, pow1, MOD1);
        b_hash1 = add_to_hash(b[i], b_hash1, BASE1, MOD1);
        
        b_hash2 = remove_from_hash(b[i - a_length], b_hash2, pow2, MOD2);
        b_hash2 = add_to_hash(b[i], b_hash2, BASE2, MOD2);
        
        if(a_hash1 == b_hash1 && a_hash2 == b_hash2){
            positions[cnt++] = i - a_length + 1;
        }
    }

    fprintf(fout, "%d\n", cnt);

    for(i = 0; i < cnt; i++){
        fprintf(fout, "%d ", positions[i]);
    }

    fclose(fin);
    fclose(fout);
    return 0;
}