Cod sursa(job #2878256)

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