Cod sursa(job #3286538)

Utilizator Robert_MitriRobert Mitri Robert_Mitri Data 14 martie 2025 12:40:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

const int nmax = 2000000;

const long long digits = 71;

unsigned int pat_hash1;
unsigned long long pat_hash2;
unsigned int txt_hash1;
unsigned long long txt_hash2;

char pat[nmax + 3];
char txt[nmax + 3];

int nrs;
vector <int> sol;

int lg;



int main()
{
    fin>>pat>>txt;

    long long p1=1,p2=1;
    for(int i=0; pat[i]; i++)
    {
        lg++;
        pat_hash1 = pat_hash1*digits + pat[i];
        pat_hash2 = pat_hash2*digits + pat[i];
        if(i!=0)
        {
            p1=p1*digits;
            p2=p2*digits;
        }

    }
    for(int i=0; txt[i]; i++)
    {
        if(i>=lg)
        {
            txt_hash1 =txt_hash1 - p1 * txt[i-lg];
            txt_hash2 =txt_hash2 - p2 * txt[i-lg];
        }
        txt_hash1 = txt_hash1*digits + txt[i];
        txt_hash2 = txt_hash2*digits + txt[i];

        if(i>=lg-1 && pat_hash1 == txt_hash1 && pat_hash2 == txt_hash2)
        {
            nrs++;
            if(sol.size()<1000)
                sol.push_back(i-lg+1);
        }
    }
    fout<<nrs<<'\n';
    for(auto& i : sol)
        fout<<i<<' ';


}