Cod sursa(job #1644328)

Utilizator RaTonAndrei Raton RaTon Data 9 martie 2016 22:32:09
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
#define mx 2000001
#define mod 666013
#define P 73
char a[mx], b[mx];
int  rez[1000], nr, na, nb, cod, has, poz;

int check(int i){
    int j;
    j = 0;
    while( a[j] == b[i] && j < na ){
        j++;
        i++;
    }
    if( j == na )
        return 1;
    else
        return 0;

}

int main(){
    int p1, i;
    fi.get(a,mx);
    fi.get();
    fi.get(b,mx);
    na = strlen(a);
    nb = strlen(b);
    if( na > nb ){
        fo << 0;
        return 0;
    }
    cod = 0;
    has = 0;
    p1 = 1;
    for( i = 0; i < na - 1; i++ ){
        cod = (cod * P + a[i]) % mod;
        has = (has * P + b[i]) % mod;
        p1 = (p1 * P) % mod;
    }
    cod = (cod * P + a[i]) % mod;
    has = (has * P + b[i]) % mod;

    if( cod == has )
        if(check(0))
            rez[nr++] = 0;

    for( i = na; i < nb; i++ ){
        poz = i - na;
        has = (( has - (p1 * b[poz]) % mod + mod) * P + b[i]) % mod;
        if( has == cod )
            if(check(poz + 1))
                if( nr < 1000 )
                    rez[nr++] = poz + 1;
                else
                    nr++;
    }
    fo << nr << "\n";
    for( i = 0; i < nr && i < 1000; i++ )
        fo << rez[i] << " ";

    return 0;
}