Cod sursa(job #2878261)

Utilizator Ana100Ana-Maria Tomoiala Ana100 Data 26 martie 2022 12:19:10
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int base=29;
const int mod=66667;
int hashA,hashB;
int power=1;
const int NMAX=2e6+5;
char a[NMAX],b[NMAX];
int lenghtA,lenghtB;
int cnt;
int solutions[1001];
int precalculate()
{
    for(int i=1;i<=lenghtA-1;i++)
    {
        power=(1LL*power*base)%mod;
    }
    return power;
}
int Create_HashA()
{
    for(int i=0;i<lenghtA;i++)
    {
        hashA=((1LL*hashA*base)%mod+a[i]-'A')%mod;
    }
}
int FindMatches()
{
    for(int i=0;i<lenghtA;i++)
    {
        hashB=((1LL*hashB*base)%mod+b[i]-'A')%mod;
    }
    if(hashB==hashA)
    {
        cnt++;
        if(cnt<=1000)
            solutions[cnt]=1;
    }
    for(int i=lenghtA;i<lenghtB;i++)
    {
        hashB=(hashB-((1LL*(b[i-lenghtA]-'A')*power)%mod)+mod)%mod;
        hashB=((1LL*hashB*base)%mod+b[i]-'A')%mod;
        if(hashA==hashB)
        {
            cnt++;
            if(cnt<=1000)
                solutions[cnt]=i-lenghtA+1;
        }
    }
}
int main()
{
    cin>>a>>b;
    lenghtA=strlen(a);
    lenghtB=strlen(b);
    precalculate();
    Create_HashA();
    FindMatches();
    cout<<cnt<<'\n';
    for(int i=1;i<=cnt;i++)
        cout<<solutions[i]<<" ";
    return 0;
}