Cod sursa(job #2878591)

Utilizator Ana100Ana-Maria Tomoiala Ana100 Data 27 martie 2022 12:47:46
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.01 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int base1=97,base2=107;
const int mod1=66667,mod2=666013;
int hashA,hashB;
int hashC,hashD;
int power1=1,power2=1;
const int NMAX=2000005;
char a[NMAX],b[NMAX];
int lenghtA,lenghtB;
int cnt;
int solutions[1002];
int precalculate1()
{
    for(int i=1;i<=lenghtA-1;i++)
    {
        power1=(1LL*power1*base1)%mod1;
    }
    return power1;
}
int precalculate2()
{
    for(int i=1;i<=lenghtA-1;i++)
    {
        power2=(1LL*power2*base2)%mod2;
    }
}
void Create_HashA()
{
    for(int i=0;i<lenghtA;i++)
    {
        hashA=((1LL*hashA*base1)%mod1+a[i])%mod1;
    }
}
void Create_HashC()
{
    for(int i=0;i<lenghtA;i++)
    {
        hashC=((1LL*hashC*base2)%mod2+a[i])%mod2;
    }
}
void FindMatches()
{
    for(int i=0;i<lenghtA;i++)
    {
        hashB=((1LL*hashB*base1)%mod1+b[i])%mod1;
    }
    for(int i=0;i<lenghtA;i++)
    {
        hashD=((1LL*hashD*base2)%mod2+b[i])%mod2;
    }
    //cout<<hashB<<" "<<hashC<<endl;
    if(hashB==hashA and hashC==hashD)
    {
        cnt++;
        if(cnt<=1000)
            solutions[cnt]=0;
    }
    for(int i=lenghtA;i<lenghtB;i++)
    {
        hashB=(hashB-((1LL*(b[i-lenghtA])*power1)%mod1)+mod1)%mod1;
        hashB=((1LL*hashB*base1)%mod1+b[i])%mod1;
        hashD=(hashD-((1LL*(b[i-lenghtA])*power2)%mod2)+mod2)%mod2;
        hashD=((1LL*hashD*base2)%mod2+b[i])%mod2;
        if(hashA==hashB and hashC==hashD)
        {
            cnt++;
            if(cnt<=1000)
                solutions[cnt]=i-lenghtA+1;
        }
    }
}
int main()
{
    cin>>a>>b;
    lenghtA=strlen(a);
    lenghtB=strlen(b);
    if(lenghtA>lenghtB)
    {
        cout<<0;
        return 0;
    }
    precalculate1();
    precalculate2();
    Create_HashA();
    Create_HashC();
    //FindMatches();
    cout<<cnt<<'\n';
    for(int i=1;i<=min(cnt,1000);i++)
        cout<<solutions[i]<<" ";
    return 0;
}