Cod sursa(job #2822033)

Utilizator ana_madalina_18Radu Ana Madalina ana_madalina_18 Data 23 decembrie 2021 14:58:12
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.03 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=666019;
int base2=89;
int mod2=714199;
/*long long pow(int a,int putere,int Mod)
{
    if(putere==1)
    {
        return a;
    }
    else if(putere%2==0)
    {
        long long p=pow(a,putere/2,Mod);
        return p*p%Mod;
    }
    else
    {
        long long p=pow(a,putere/2,Mod);
        return a*p*p%Mod;
    }
}*/
long long Hash(int st, int dr, const string & x,int Base,int Mod)
{
    long long rasp=0;
    long long p=1;
    for(int i=dr;i>=st;i--)
    {
        rasp=rasp+x[i]*p;
        rasp=rasp%Mod;
        p=p*Base;
        p=p%Mod;
    }
    return rasp;
}
void avanseaza_hash(int & hash_b, int putere, int Mod, int Base, char urm, char primul)
{
    hash_b=(hash_b-(1LL*primul*putere)%Mod+Mod)%Mod;
    hash_b=(hash_b*Base)%Mod;
    hash_b+=urm;
    hash_b=hash_b%Mod;
}
int main()
{
    fin>>a;
    fin>>b;
    int lung_a=a.size();
    int lung_b=b.size();
    long long h_a=Hash(0,lung_a-1,a,97,666019);
    long long h_a2=Hash(0,lung_a-1,a,89,714199);

    int h_b=Hash(0,lung_a-1,b,97,666019);
    int h_b2=Hash(0,lung_a-1,b,89,714199);

    int putere=1;
    int putere2=1;

    for(int i=1;i<lung_a;i++)
    {
        putere=(1LL*putere*base)%mod;
        putere2=(1LL*putere2*base2)%mod2;
    }

    int primul=0;

    if(h_a==h_b && h_a2==h_b2)
    {
        v.push_back(0);
    }
    for(int i=lung_a;i<lung_b;i++)
    {
        avanseaza_hash(h_b,putere,mod,base,b[i],b[primul]);
        avanseaza_hash(h_b2,putere2,mod2,base2,b[i],b[primul]);

        primul++;

        if(h_a==h_b && h_a2==h_b2)
        {
            v.push_back(primul);
        }

        if(v.size()==1000)
        {
            break;
        }
    }
    fout<<v.size()<<'\n';

    for(int i=0;i<v.size();i++)
    {
        fout<<v[i]<<' ';
    }
    return 0;
}