Cod sursa(job #3149120)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 6 septembrie 2023 15:01:42
Problema Potrivirea sirurilor Scor 92
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.23 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 + (A[i]-'A'+1)) % MOD1;
            hashA2 = ((long long)hashA2 * BAZA % MOD2 + (A[i]-'A'+1)) % MOD2;
        }
        //cout<<hashA1<<" "<<hashA2<<"\n";

        hashB1 = hashB2 = 0;
        for(int i=0; i < sizeA-1; i++){
            hashB1 = ((long long)hashB1 * BAZA % MOD1 + (B[i]-'A'+1)) % MOD1;
            hashB2 = ((long long)hashB2 * BAZA % MOD2 + (B[i]-'A'+1)) % 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 + (B[i]-'A'+1)) % MOD1;
            hashB2 = ((long long)hashB2 * BAZA % MOD2 + (B[i]-'A'+1)) % MOD2;

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

            //cout<<i-sizeA+1<<" -> "<<i<<"\n";
            hashB1 = ((long long)hashB1 - (long long)(B[i-sizeA+1]-'A'+1) * precalc1 % MOD1 + MOD1) % MOD1;
            hashB2 = ((long long)hashB2 - (long long)(B[i-sizeA+1]-'A'+1) * precalc2 % MOD2 + MOD2) % MOD2;
        }
    }

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