Cod sursa(job #2974190)

Utilizator mihnea_mihneaGrigore Mihnea mihnea_mihnea Data 3 februarie 2023 15:30:45
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <cstring>

#define MAX 20000001
#define MOD1 666013
#define MOD2 100003
#define BAZA 62

using namespace std;

char A[MAX], B[MAX];

char gasit[MAX];

int main()
{
    int nr1,nr2,i,a1=0,a2=0,b1=0,b2=0,k=0,baza1=1,baza2=1;

    cin.getline(A,MAX-1);
    cin.getline(B,MAX-1);

    nr1=strlen(A);
    nr2=strlen(B);

    for(i=0;i<nr1;i++)
    {
        a1=(a1*BAZA+A[i])%MOD1;
        a2=(a2*BAZA+A[i])%MOD2;
        if(i>0)
            baza1=(baza1*BAZA)%MOD1, baza2=(baza2*BAZA)%MOD2;
    }
    if(nr1>nr2)
        cout<<0;
    else
    {
        for(i=0;i<nr1;i++)
        {
            b1=(b1*BAZA+B[i])%MOD1;
            b2=(b2*BAZA+B[i])%MOD2;
        }
        if(a1==b1 && a2==b2)
            gasit[0]=1, k++;
        for(i=nr1;i<nr2;i++)
        {
            b1=((b1-(B[i-nr1]*baza1)%MOD1+MOD1)*BAZA+B[i])%MOD1;
            b2=((b2-(B[i-nr1]*baza2)%MOD2+MOD2)*BAZA+B[i])%MOD2;

            if(a1==b1 && a2==b2)
                gasit[i-nr1+1]=1, k++;
        }
        cout<<k<<'\n';
        k=0;
        for(i=0;i<nr2;i++)
        {
            if(gasit[i])
                cout<<i<<" ", k++;
            if(k>=1001)
                break;
        }
    }
    return 0;
}