Cod sursa(job #3258927)

Utilizator Alexbora13Bora Ioan Alexandru Alexbora13 Data 24 noiembrie 2024 12:49:11
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 2000000;
const int mod1 = 100007;
const int mod2 = 100021;
const int b    = 73;

string A;
string B;
int este[NMAX+1];
int pow1 = 1, pow2 = 1;
int hashA1, hashA2;
int hashB1, hashB2;

int main()
{
    ios::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);   
    fin >> A;
    fin >> B;
    int szA = A.size();
    int szB = B.size();
    for(int i=0; i<szA; i++)
    {
        if(i!=0)
            pow1 = (pow1*b)%mod1,
            pow2 = (pow2*b)%mod2;
        hashA1 = (hashA1*b + A[i])%mod1;
        hashA2 = (hashA2*b + A[i])%mod2;
    }
    int cnt = 0;
    for(int i=0; i<szA; i++)
        hashB1 = (hashB1*b + B[i])%mod1,
        hashB2 = (hashB2*b + B[i])%mod2;

    if(hashA1 == hashB1 && hashA2 == hashB2)
        este[0] = 1, cnt++;    
    
    for(int i=szA; i<szB; i++)
    {
        hashB1 = ((hashB1 - (B[i-szA]*pow1) % mod1 + mod1)*b+B[i])%mod1;
        hashB2 = ((hashB2 - (B[i-szA]*pow2) % mod2 + mod2)*b+B[i])%mod2;
        
        //cout << hashB1 << ' ' << hashB2 << '\n';

        if(hashA1 == hashB1 && hashA2 == hashB2)
            este[i-szA+1] = 1, cnt++;
    }
    fout << cnt << '\n';
    cnt  = 1;
    for(int i=0; i<szB && cnt<1000; i++)
        if(este[i])
            fout << i << ' ', cnt++;
    return 0;
}