Cod sursa(job #3199646)

Utilizator monica_LMonica monica_L Data 2 februarie 2024 10:44:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#include <fstream>
#include <vector>
#include <string>

#define M1 1000000013
#define M2 1000000007
#define PRIM1 37
#define PRIM2 31

using namespace std;

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

string A, B;
vector <int> rez;
unsigned long long hashA1, hashA2, P1 = 1, P2 = 1, hashB1, hashB2;
int szA, szB, nr = 0;

int main()
{
    f >> A >> B;
    szA = A.size();
    szB = B.size();

    if (szA > szB)
    {
        g << "0";
        return 0;
    }

    //hashuri pentru sirul A
    for(int i=0; i<szA; ++i)
    {
        hashA1 = ((hashA1 * PRIM1) % M1 + A[i]) % M1;
        hashA2 = ((hashA2 * PRIM2) % M2 + A[i]) % M2;

        if(i!=0)
        {
            P1 = (P1 * PRIM1) % M1;
            P2 = (P2 * PRIM2) % M2;
        }
    }

    //hashuri pentru primele szA caractere din B
    for(int i=0; i<szA; ++i)
    {
        hashB1 = ((hashB1 * PRIM1) % M1 + B[i]) % M1;
        hashB2 = ((hashB2 * PRIM2) % M2 + B[i]) % M2;
    }

    if(hashA1 == hashB1 && hashA2 == hashB2)
    {
        rez.push_back(0);
        ++nr;
    }

    //Restul de subsiruri de lungime szA
    for(int i=szA; i<=szB; ++i)
    {
        hashB1 = ((PRIM1 * (hashB1 - ((B[i - szA] * P1) % M1) + M1)) % M1 + B[i]) % M1;
        hashB2 = ((PRIM2 * (hashB2 - ((B[i - szA] * P2) % M2) + M2)) % M2 + B[i]) % M2;

        if(hashB1 == hashA1 && hashB2 == hashA2)
        {
            rez.push_back(i - szA + 1);
            nr++;
        }
    }

    g << nr << '\n';
    for(int i=0; i<rez.size() && i<1000; ++i)
        g << rez[i] << ' ';

    return 0;
}