Cod sursa(job #2809549)

Utilizator FeliciaicarRusu Felician Gabriel Feliciaicar Data 27 noiembrie 2021 10:49:02
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include <iostream>
#include <string.h>
#include <fstream>

using namespace std;

int l1,l2;
char s1[2000005],s2[2000005];
long long a[1005];

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

struct Hash
{
    long long n,mod,power,value;
    Hash(){
        n=0;
        mod=0;
        power=0;
        value=0;
    }
    void init(char *s, long long len)
    {
        power=1;
        value=0;
        for(long long i=len-1;i>=0;i--){
            value=(value+(1ll * power * s[i])%mod)%mod;
            if(i)
                power=(power*n)%mod;
        }
    }
    void roll(char toRemove, char toAdd)
    {
        value=(((value-(1ll * toRemove * power)%mod + mod)*n)%mod + toAdd)%mod;
    }
};

int main()
{
    fin.getline(s1,2000005);
    fin.getline(s2,2000005);
    l1=strlen(s1);
    l2=strlen(s2);
    Hash pHash, tHash;
    pHash.n=31;
    pHash.mod=40099;
    tHash.n=31;
    tHash.mod=40099;
    Hash hHash,oHash;
    hHash.n=53;
    hHash.mod=319993;
    oHash.n=53;
    oHash.mod=319993;
    long long nr=0;
    pHash.init(s1,l1);
    tHash.init(s2,l1);
    hHash.init(s1,l1);
    oHash.init(s2,l1);
    if(pHash.value==tHash.value && hHash.value==oHash.value)
    {
        a[++nr]=0;
    }
    for(long long i=l1;i<l2;i++){
        tHash.roll(s2[i-l1],s2[i]);
        oHash.roll(s2[i-l1],s2[i]);
        if(tHash.value==pHash.value && hHash.value==oHash.value)
        {
            if(nr<=1000)
                a[++nr]=(i-l1+1);
            else
                nr++;
        }
    }
    fout<<nr<<endl;
    for(int i=1;i<=nr;i++)
        fout<<a[i]<<" ";
    return 0;
}