Cod sursa(job #3291643)

Utilizator Luca_georgescuLucageorgescu Luca_georgescu Data 5 aprilie 2025 11:14:37
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda cex_9 Marime 1.21 kb
#include <bits/stdc++.h>

#define mod1 666013
#define mod2 10003
#define bz 67

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

bool ok[2000001];
char a[2000001],b[2000001];

int na,nb,h1,h2,v1,v2,bz1,bz2,nr;

int main()
{
    f >> a >> b;

    na=strlen(a);
    nb=strlen(b);

    if ( na>nb )
    {
        g << 0;
        return 0;
    }

    bz1=1;
    bz2=1;

    for (int i=0; i<na; i++ )
    {
        h1=(h1*bz+a[i])%mod1;
        h2=(h2*bz+a[i])%mod2;

        if ( i>0 )
        {
            bz1=(bz1*bz)%mod1;
            bz2=(bz2*bz)%mod2;
        }

        v1=(v1*bz+b[i])%mod1;
        v2=(v2*bz+b[i])%mod2;
    }

    if ( v1==h1 && v2==h2 )
    {
        ok[0]=true;
        nr++;
    }

    for (int i=na; i<nb; i++ )
    {
        v1=((v1-(b[i-na]*bz1)%mod1+mod1)*bz+b[i])%mod1;
        v2=((v2-(b[i-na]*bz2)%mod2+mod2)*bz+b[i])%mod2;

        if ( v1==h1 && v2==h2 )
        {
            ok[i-na+1]=true;
            nr++;
        }
    }

    g << nr;
    g << '\n';

    nr=0;
    for (int i=0; i<nb && nr<1000; i++ )
        if ( ok[i] ){
             nr++;
             g << i << " ";
         }
    return 0;
}