Cod sursa(job #2839320)

Utilizator Darius1414Dobre Darius Adrian Darius1414 Data 25 ianuarie 2022 19:28:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>
#define nmax 2000005
#define mod1 98999
#define mod2 99991
#define baza 123
using namespace std;
char A[nmax],B[nmax];
int V[nmax],P[nmax],rsp[nmax];
int ma,mb,h1,h2;
int main()
{
    ifstream f ("strmatch.in");
    ofstream g ("strmatch.out");
    f>>A>>B;
    ma=strlen(A);
    mb=strlen(B);
    int r1=0,r2=0,inm1=1,inm2=1,sol=0;
    for (int i=0; i<ma; i++)
    {
        r1=(r1*baza+A[i])%mod1;
        r2=(r2*baza+A[i])%mod2;
        h1=(h1*baza+B[i])%mod1;
        h2=(h2*baza+B[i])%mod2;
        if (i==ma-1 && r1==h1 && r2==h2)
            sol++,rsp[sol]=i-ma+1;
        if (i!=0)
        {
            inm1=(inm1*baza)%mod1;
            inm2=(inm2*baza)%mod2;
        }
    }
    for (int i=ma; i<mb; i++)
    {
        h1=h1-(B[i-ma]*inm1)%mod1+mod1;
        h2=h2-(B[i-ma]*inm2)%mod2+mod2;
        h1=(h1*baza+B[i])%mod1;
        h2=(h2*baza+B[i])%mod2;
        if (r1==h1 && r2==h2)
            sol++,rsp[sol]=i-ma+1;
    }
    g<<sol<<'\n';
    sol=min(sol,1000);
    for (int i=1; i<=sol; i++)
        g<<rsp[i]<<' ';
}