Cod sursa(job #2030726)

Utilizator nedelcu11Nedelcu Mihai Vlad nedelcu11 Data 2 octombrie 2017 08:48:03
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

string A,B;

vector <int> rez;
int baza=73;
int MOD2=10000007;
int MOD=666013;
int hashA,hashB,hashB2,hashA2,cnt;

int main()
{
    f>>A>>B;
    int putere=1,putere2=1,i;
    for(i=0; i<A.size(); i++)
    {
        hashA = (hashA*baza + A[i]) % MOD;
        hashA2 = (hashA2*baza + A[i]) % MOD2;
        if(i!=0)
        {
        putere = (putere*baza)%MOD;
        putere2 = (putere2*baza)%MOD2;
        }
    }

    for(i=0; i<A.size(); i++)
    {
        hashB = (hashB*baza+B[i]) % MOD;
        hashB2 = (hashB2*baza+B[i]) % MOD2;
    }

    if(hashA==hashB&&hashA2==hashB2)
        {
            cnt++;
            rez.push_back(0);
        }
    for(i=A.size(); i<B.size(); i++)
    {
         hashB = ((hashB - (B[i - A.size()] * putere) % MOD + MOD) * baza + B[i]) % MOD;
         hashB2 = ((hashB2 - (B[i - A.size()] * putere2) % MOD2 + MOD2) * baza + B[i]) % MOD2;
        if(hashA==hashB && hashA2==hashB2)
        {
            cnt++;
            if(cnt<=1000)
                rez.push_back(i-A.size()+1);
        }
    }
    g<<cnt<<'\n';
    for(auto it:rez)
        g<<it<<" ";
    return 0;
}