Cod sursa(job #2951219)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 5 decembrie 2022 18:41:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <bits/stdc++.h>

using namespace std;

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

const int P = 73;
const int MOD1 = 666013;
const int MOD2 = 666017;
int hashA1, hashA2, hash1, hash2, P1, P2;

const int OUT = 1000;
const int LIM = 2e6;
string a, b;
int asize, bsize;
int out, sol[OUT + 5];

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

    ///il caut pe a in b
    fin>>a>>b;
    a = " " + a, asize = (int)a.size() - 1;
    b = " " + b, bsize = (int)b.size() - 1;

    P1 = P2 = 1;
    hashA1 = hashA2 = 0;
    for(int i=1; i<=asize; i++){
        hashA1 = (hashA1 * P + (int)a[i]) % MOD1;
        hashA2 = (hashA2 * P + (int)a[i]) % MOD2;

        if(i != 1){
            P1 = (P1 * P) % MOD1;
            P2 = (P2 * P) % MOD2;
        }
    }

    hash1 = hash2 = 0;
    for(int i=1; i<=bsize; i++){
        hash1 = (hash1 * P + (int)b[i]) % MOD1;
        hash2 = (hash2 * P + (int)b[i]) % MOD2;

        if(i >= asize){
            if(hash1 == hashA1 && hash2 == hashA2){
                out++;
                if(out <= OUT)
                    sol[out] = i-asize;
            }

            hash1 = (hash1 - ((int)b[i-asize+1] * P1) % MOD1 + MOD1) % MOD1;
            hash2 = (hash2 - ((int)b[i-asize+1] * P2) % MOD2 + MOD2) % MOD2;
        }
    }

    fout<<out<<"\n";
    for(int i=1; i<=min(out, OUT); i++)
        fout<<sol[i]<<" ";
    return 0;
}