Cod sursa(job #2294356)

Utilizator refugiatBoni Daniel Stefan refugiat Data 2 decembrie 2018 12:17:49
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream si("strmatch.in");
ofstream so("strmatch.out");
#define MAXN 2000005
#define p 73
#define MOD1 100007
#define MOD2 100021
string a, b;
int na, nb;
int hashA1, hashA2, p1, p2;
bool match[MAXN];
int main()
{
    si>>a>>b;
    na=a.size();
    nb=b.size();
    p1=p2=1;
    hashA1=hashA2=0;
    for(int i=0; i<na; ++i) {
        hashA1=(hashA1*p+a[i])%MOD1;
        hashA2=(hashA2*p+a[i])%MOD2;
        if(i!=0) {
            p1=(p1*p)%MOD1;
            p2=(p2*p)%MOD2;
        }
    }
    if(na>nb) {
        so<<0;
        return 0;
    }
    int hash1=0, hash2=0;
    for(int i=0; i<na; ++i) {
        hash1=(hash1*p+b[i])%MOD1;
        hash2=(hash2*p+b[i])%MOD2;
    }
    int nr=0;
    if(hash1==hashA1&&hash2==hashA2) {
        match[0]=true;
        nr++;
    }
    for(int i=na; i<nb; ++i) {
        hash1=((hash1-(b[i-na]*p1)%MOD1+MOD1)*p+b[i])%MOD1;
        hash2=((hash2-(b[i-na]*p2)%MOD2+MOD2)*p+b[i])%MOD2;
        if(hash1==hashA1&&hash2==hashA2) {
            match[i-na+1]=1;
            ++nr;
        }

    }
    so<<nr<<'\n';
    nr=0;
    for(int i=0; i<nb&&nr<1000; ++i)
        if(match[i]) {
            nr++;
            so<<i<<' ';
        }
    return 0;
}