Cod sursa(job #3149121)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 6 septembrie 2023 15:07:25
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.06 kb
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("popcnt")

using namespace std;

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

const int BAZA = 73;
const int MOD1 = 666013;
const int MOD2 = 666017;

string A, B;
int sizeA, hashA1, hashA2;
int sizeB, hashB1, hashB2, precalc1, precalc2;
int sol;
queue<int> output;

static inline int lgput(int a, int b, int MOD){
    int sol = 1;
    while(b != 0){
        if(b & 1)
            sol = (long long)sol * a % MOD;
        a = (long long)a * a % MOD;
        b >>= 1;
    }
    return sol;
}

int main (){
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr), fout.tie(nullptr);

    fin>>A>>B;
    sizeA = (int)A.size();
    sizeB = (int)B.size();

    if(sizeA <= sizeB){
        hashA1 = hashA2 = 0;
        for(int i=0; i < sizeA; i++){
            hashA1 = ((long long)hashA1 * BAZA % MOD1 + (int)A[i]) % MOD1;
            hashA2 = ((long long)hashA2 * BAZA % MOD2 + (int)A[i]) % MOD2;
        }

        hashB1 = hashB2 = 0;
        for(int i=0; i < sizeA-1; i++){
            hashB1 = ((long long)hashB1 * BAZA % MOD1 + (int)B[i]) % MOD1;
            hashB2 = ((long long)hashB2 * BAZA % MOD2 + (int)B[i]) % MOD2;
        }

        precalc1 = lgput(BAZA, sizeA-1, MOD1);
        precalc2 = lgput(BAZA, sizeA-1, MOD2);
        for(int i=sizeA-1; i < sizeB; i++){
            hashB1 = ((long long)hashB1 * BAZA % MOD1 + (int)B[i]) % MOD1;
            hashB2 = ((long long)hashB2 * BAZA % MOD2 + (int)B[i]) % MOD2;

            if(hashB1 == hashA1 && hashB2 == hashA2){
                sol++;
                if(sol <= 1000)
                    output.push(i-sizeA+1);
            }

            hashB1 = ((long long)hashB1 - (long long)B[i-sizeA+1] * precalc1 % MOD1 + MOD1) % MOD1;
            hashB2 = ((long long)hashB2 - (long long)B[i-sizeA+1] * precalc2 % MOD2 + MOD2) % MOD2;
        }
    }

    fout<<sol<<"\n";
    while(!output.empty()){
        fout<<output.front()<<" ";
        output.pop();
    }
    return 0;
}