Cod sursa(job #2819537)

Utilizator ana_madalina_18Radu Ana Madalina ana_madalina_18 Data 18 decembrie 2021 15:48:03
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
vector <int> v;
int base=97;
int mod=666013;
int pow(int a,int putere)
{
    if(putere==1)
    {
        return a;
    }
    else if(putere%2==0)
    {
        return pow(a,putere/2)*pow(a,putere/2);
    }
    else
    {
        return a*pow(a,putere/2)*pow(a,putere/2);
    }
}
int Hash(int st, int dr, const string & x)
{
    int rasp=0;
    int p=1;
    for(int i=st;i<=dr;i++)
    {
        rasp=rasp+x[i]*p;
        rasp=rasp%mod;
        p=p*base;
        p=p%mod;
    }
    return rasp;
}
int main()
{
    fin>>a;
    fin>>b;
    int lung_a=a.size();
    int h_a=Hash(0,lung_a-1,a);
    int h_b=Hash(b.size()-lung_a,b.size()-1,b);
    int putere=pow(base,a.size()-1);
    int ult=b.size()-1;
    for(int i=b.size()-lung_a;i>=0;i--)
    {
        if(h_b==h_a)
        {
            v.push_back(i);
        }
        if(i!=0)
        {
            h_b-=b[ult]*putere%mod;
            h_b=(h_b+mod)%mod;
            h_b*=base;
            h_b+=b[i-1];
            h_b=h_b%mod;
            ult--;
        }
    }
    fout<<v.size()<<'\n';
    reverse(v.begin(),v.end());
    int lung_v=v.size();
    int dist=min(1000,lung_v);
    for(int i=0;i<dist;i++)
    {
        fout<<v[i]<<' ';
    }
    return 0;
}