Cod sursa(job #2721832)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 12 martie 2021 12:19:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.87 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

const long long p = 73;
const long long MODULO1 = 100007;
const long long MODULO2 = 100021;

const int SOLDIMMAX = 1000;

string sir1, sir2;

vector<int> sol;

/// Rabin-Karp

int main()
{
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");

    in >> sir1 >> sir2;

    long long hash1 = 0;
    long long hash2 = 0;

    long long p1 = 1;
    long long p2 = 1;

    for (int i = 0; i < sir1.size(); i++)
    {
        hash1 = (hash1 * p + sir1[i]) % MODULO1;
        hash2 = (hash2 * p + sir1[i]) % MODULO2;

        if (i > 0)
        {
            p1 = (p1 * p) % MODULO1;
            p2 = (p2 * p) % MODULO2;
        }
    }

    if (sir1.size() > sir2.size())
    {
        out << 0 << '\n';

        return 0;
    }

    long long nrAparitii = 0;

    long long hash1Crt = 0;
    long long hash2Crt = 0;

    for (int i = 0; i < sir1.size(); i++)
    {
        hash1Crt = (hash1Crt * p + sir2[i]) % MODULO1;
        hash2Crt = (hash2Crt * p + sir2[i]) % MODULO2;
    }

    if (hash1 == hash1Crt && hash2 == hash2Crt)
    {
        nrAparitii++;

        sol.emplace_back(0);
    }

    for (int i = sir1.size(); i < sir2.size(); i++)
    {
        hash1Crt = ((hash1Crt - (p1 * sir2[i - sir1.size()]) % MODULO1 + MODULO1) * p + sir2[i]) % MODULO1;
        hash2Crt = ((hash2Crt - (p2 * sir2[i - sir1.size()]) % MODULO2 + MODULO2) * p + sir2[i]) % MODULO2;

        if (hash1 == hash1Crt && hash2 == hash2Crt)
        {
            nrAparitii++;

            if (nrAparitii <= SOLDIMMAX)
            {
                sol.emplace_back(i - sir1.size() + 1);
            }
        }

    }

    out << nrAparitii << '\n';

    for (int i = 0; i < sol.size(); i++)
    {
        out << sol[i] << ' ';
    }

    return 0;
}