Cod sursa(job #3231666)

Utilizator Luca_georgescuLucageorgescu Luca_georgescu Data 27 mai 2024 15:48:25
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>

#define mod1 666013
#define mod2 10003
#define bz 127

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;
}