Cod sursa(job #2787463)

Utilizator sandifx68Fazakas Alexandru sandifx68 Data 23 octombrie 2021 13:28:49
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

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

char unu[2000001],doi[2000001];
long long a[1001];
int nr,l1,l2;

struct h{
    long long hvalue=0,m=319993,n=37,pow=1;
    void init(char s[], int len){
        pow=1;hvalue=0;
        for(int i=len-1;i>=0;i--){
            hvalue=(hvalue+(pow*s[i])%m)%m;
            if(i)
                pow*=n;
        }
    }
    void roll(char toR, char toA){
        hvalue=(((hvalue-(toR*pow)%m+m)*n)%m+toA)%m;
    }
    bool operator==(const h&other) const{
        return hvalue==other.hvalue;
    }

}shor,lo;

void solve(char s1[],char s2[]){
    shor.init(s1,l1);
    lo.init(s2,l1);
    if(shor==lo)
        a[nr++]=0;
    for(int i=l1;i<l2;i++){
        lo.roll(s2[i-l1],s2[i]);
        if(lo==shor){
            if(nr<=1000)
                a[nr++]=i-l1+1;
            else nr++;
        }
    }
}



int main()
{
    f.getline(unu,2000001);
    f.getline(doi,2000001);
    l1=strlen(unu);l2=strlen(doi);
    solve(unu,doi);
    g<<nr<<"\n";
    for(int i=0;i<(nr<=1000?nr:1000);i++)
        g<<a[i]<<" ";
}