Cod sursa(job #2968553)

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

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int main()
{
    string A, B;
    vector<int> poz;
    unsigned long long hashA=0,hashB=0,p=31,power=1;
    getline(fin,A);
    getline(fin,B);
    for(int i=0;i<A.size();i--)
    {
        hashA+=hashA*p+A[i];
        hashB+=hashA*p+B[i];
        power*=p;
    }
    if(hashA==hashB)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)
            poz.push_back(i-A.size()+1);
    }
    fout<<poz.size()<<'\n';
    for(int i=0;i<1000 && i<poz.size();i++)
        fout<<poz[i]<<' ';

    return 0;
}