Cod sursa(job #3206238)

Utilizator AndreasBossGamerBaragau Andreas AndreasBossGamer Data 22 februarie 2024 00:34:59
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <fstream>
#include <queue>
#include <string>
#define PUTERE 10
#define PUTERE2 29
#define MOD 100007

using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

string s1, s2;
queue<int> rez;
int cnt = 0;

int main()
{
    ///citire
    cin >> s1 >> s2;

    ///daca primul string este mai lung
    if (s1.size() > s2.size())
    {
        cout << 0;
        return 0;
    }

    ///calculez hash urile la primul sir
    int hashPrim1 = 0, hashPrim2 = 0;
    int hashSecund1 = 0, hashSecund2 = 0;

    int P1 = 1, P2 = 1;
    int size1 = s1.size();
    for (int i = 0; i < size1; i++) {
        hashPrim1 = (hashPrim1 * PUTERE + s1[i]) % MOD;
        hashPrim2 = (hashPrim2 * PUTERE2 + s1[i]) % MOD;
        hashSecund1 = (hashSecund1 * PUTERE + s2[i]) % MOD;
        hashSecund2 = (hashSecund2 * PUTERE2 + s2[i]) % MOD;
        if (i != 0)
        { 
            P1 = (P1 * PUTERE) % MOD;
            P2 = (P2 * PUTERE2) % MOD;
        }
    }

    if (hashPrim1 == hashSecund1 && hashPrim2 == hashSecund2)
    {
        rez.push(1);
        cnt++;
    }
    for (int i = size1; i < s2.size(); i++)
    {
        hashSecund1 = ((hashSecund1 - (s2[i - size1] * P1) % MOD + MOD) * PUTERE + s2[i]) % MOD;
        hashSecund2 = ((hashSecund2 - (s2[i - size1] * P2) % MOD + MOD) * PUTERE2 + s2[i]) % MOD;
        if (hashPrim1 == hashSecund1 && hashPrim2 == hashSecund2)
        {
            rez.push(i + 1 - size1);
            cnt++;
        }
    }

    cout << cnt << '\n';
    cnt = 0;
    while (!rez.empty() && cnt <= 1000) {
        cout << rez.front() << " ";
        rez.pop();
        cnt++;
    }
}