Cod sursa(job #2543589)

Utilizator Arsene_DenisaArsene Denisa Arsene_Denisa Data 11 februarie 2020 11:56:48
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <iostream>
#include<fstream>
#include<cstring>

#define MOD1 100007
#define MOD2 100021

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

int i, j, na, nb, ns1, ns2, nsa1, nsa2, p1, p2, nr;

using namespace std;

int main() {

    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    fin.getline(a, 2000001);
    fin.getline(b, 2000001);
    na=strlen(a);
    nb=strlen(b);
    p1=p2=1;
    nsa1=nsa2=0;
    for(i=0;i<na;i++) {
            nsa1=(nsa1*73+a[i])%MOD1;
    nsa2=(nsa2*73+a[i])%MOD2;
    if(i!=0) {
            p1=(p1*73)%MOD1;
    p2=(p2*73)%MOD2;
    }
    }
    if(na>nb) {
            fout<<"0";
    }
    else {
         ns1=ns2=0;
    for(i=0;i<na;i++) {
            ns1=(ns1*73+b[i])%MOD1;
    ns2=(ns2*73+b[i])%MOD2;
    }
    nr=0;
    if(ns1==nsa1 && ns2==nsa2) {
            ok[0]=1;
            nr++;
    }
    for(i=na;i<nb;i++) {
           ns1=((ns1-(b[i-na]*p1)%MOD1+MOD1)*73+b[i])%MOD1;
           ns2=((ns2-(b[i-na]*p2)%MOD2+MOD2)*73+b[i])%MOD2;
           if(ns1==nsa1 && ns2==nsa2) {
                ok[i-na+1]=1;
           nr++;
           }
    }
    fout<<nr<<endl;
    nr=0;
    for(i=0;i<nb && nr<1000;i++) {
            if(ok[i]) {
                 fout<<i<<" ";
                    nr++;
            }
    }
    }
    return 0;
}