Cod sursa(job #1651016)

Utilizator RaTonAndrei Raton RaTon Data 11 martie 2016 23:02:49
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
#define mx 2000001
#define mod1 100021
#define mod2 100007
#define P 83
char a[mx], b[mx];
int  rez[1000], nr, na, nb, cod1, cod2, has1, has2, poz;


int main(){
    int p1, p2, i;
    fi.get(a,mx);
    fi.get();
    fi.get(b,mx);
    na = strlen(a);
    nb = strlen(b);
    if( na > nb ){
        fo << 0;
        return 0;
    }
    cod1 = cod2 = 0;
    has1 = has2 = 0;
    p1 = 1;
    p2 = 1;
    for( i = 0; i < na - 1; i++ ){
        cod1 = (cod1 * P + a[i]) % mod1;
        cod2 = (cod2 * P + a[i]) % mod2;
        has1 = (has1 * P + b[i]) % mod1;
        has2 = (has2 * P + b[i]) % mod2;
        p1 = (p1 * P) % mod1;
        p2 = (p2 * P) % mod2;
    }
    cod1 = (cod1 * P + a[i]) % mod1;
    cod2 = (cod2 * P + a[i]) % mod2;
    has1 = (has1 * P + b[i]) % mod1;
    has2 = (has2 * P + b[i]) % mod2;

    nr = 0;
    if( cod1 == has1 && cod2 == has2  )
        rez[nr++] = 0;

    for( i = na; i < nb; i++ ){
        poz = i - na;
        has1 = (( has1 - (p1 * b[poz]) % mod1 + mod1) * P + b[i]) % mod1;
        has2 = (( has2 - (p2 * b[poz]) % mod2 + mod2) * P + b[i]) % mod2;
        if( has1 == cod1 && has2 == cod2 ){
            if( nr < 1000 )
                rez[nr] = poz + 1;
            nr++;
        }

    }
    fo << nr << "\n";
    for( i = 0; i < nr && i < 1000; i++ )
        fo << rez[i] << " ";

    return 0;
}