Cod sursa(job #2469457)

Utilizator vladbatalanBatalan Vlad vladbatalan Data 7 octombrie 2019 12:50:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <bits/stdc++.h>
#define P 73
#define MOD1 100007
#define MOD2 100021

using namespace std;

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

string a, b;
int NA, NB;

int hashA1, hashA2, P1, P2;
int hash1, hash2, sz;
vector<int> sol;


int main()
{
    fin >> a >> b;
    NA = a.size();
    NB = b.size();

    P1 = P2 = 1;
    hashA1 = hashA2 = 0;

    ///hashuiesc dublu patternul A
    for(int i=0; i<NA; i++)
    {
        hashA1 = (hashA1 * P + a[i]) % MOD1;
        hashA2 = (hashA2 * P + a[i]) % MOD2;
        if(i!=0)
        {
            P1 = (P1 * P)%MOD1;
            P2 = (P2 * P)%MOD2;
        }
    }
    if(NA > NB) /// nu are rost
    {
        fout << 0 << '\n';
        return 0;
    }

    ///hashuiesc primul segment din s
    hash1 = hash2 = 0;
    for(int i=0; i<NA; i++)
    {
        hash1 = (hash1 * P + b[i])%MOD1;
        hash2 = (hash2 * P + b[i])%MOD2;
    }
    ///verificam primul pattern
    if(hash1 == hashA1 && hash2 == hashA2)
        sol.push_back(0);

    ///creez cate un hash pe rand si verific
    for(int i=NA; i<NB; i++)
    {
        hash1 = (((hash1 - b[i-NA] * P1) % MOD1 + MOD1) * P + b[i]) % MOD1;
        hash2 = (((hash2 - b[i-NA] * P2) % MOD2 + MOD2) * P + b[i]) % MOD2;

        if(hash1 == hashA1 && hash2 == hashA2)
            sol.push_back(i-NA+1);
    }

    ///afisarea solutiilor
    sz = sol.size();
    fout << sz << '\n';
    for(int i=0; i < sz && i < 1000; i++)
        fout << sol[i] << ' ';

    return 0;
}