Cod sursa(job #2968547)

Utilizator patrickunudoiBeres Patrick Stefan patrickunudoi Data 21 ianuarie 2023 15:09:05
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int main()
{
    string A, B;
    vector<int> poz;
    int nr=0;
    unsigned int hashA=0,hashB=0,p=13,power=1;
    getline(fin,A);
    getline(fin,B);
    for(int i=A.size()-1;i>=0;i--)
    {
        hashA+=power*A[i];
        hashB+=power*B[i];
        power*=p;
    }
    if(hashA==hashB)nr++,poz.push_back(0);
    for(int i=A.size();i<B.size();i++)
    {

        hashB=hashB*p-B[i-A.size()]*power+B[i];

        if(hashA==hashB)nr++,poz.push_back(i-A.size()+1);
    }
    fout<<nr<<'\n';
    for(int i=0;i<1000 && i<poz.size();i++)
        fout<<poz[i]<<' ';

    return 0;
}