Cod sursa(job #2786967)

Utilizator filiptudose2007Tudose Filip filiptudose2007 Data 22 octombrie 2021 10:12:09
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>
using namespace std;
const int Mod1=666013;
const int Mod2=10003;
const int p=109;
char a[2000005],b[2000005];
int rez[2000005],nr;
long long h1,h2,v1,v2,putere1,putere2;
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    cin.sync_with_stdio(false);
    cin.tie(0);
    cin>>a>>b;
    int m=strlen(a);
    int n=strlen(b);
    h1=h2=a[0]-'0';
    putere1=putere2=1;
    for(int i=1; i<m; ++i)
    {
        h1=(h1*p+a[i]-'0')%Mod1;
        h2=(h2*p+a[i]-'0')%Mod2;
        putere1=(putere1*p)%Mod1;
        putere2=(putere2*p)%Mod2;
    }
    for(int i=0; i<m; ++i)
    {
        v1=(v1*p+b[i]-'0')%Mod1;
        v2=(v2*p+b[i]-'0')%Mod2;
    }
    if(v1==h1 && v2==h2)
    {
        rez[++nr]=0;
    }
    for(int i=m; i<n; ++i)
    {
        v1=(1LL*(v1-(1LL*putere1*(b[i-m]-'0'))%Mod1+Mod1)*p+b[i]-'0')%Mod1;
        v2=(1LL*(v2-(1LL*putere2*(b[i-m]-'0'))%Mod2+Mod2)*p+b[i]-'0')%Mod2;
        if(v1==h1 && v2==h2)
        {
            rez[++nr]=i-m+1;
        }
    }
    cout<<nr<<'\n';
    for(int i=1; i<=nr; ++i)
    {
        cout<<rez[i]<<' ';
    }
    return 0;
}