Cod sursa(job #626435)

Utilizator theodora_maneaManea Theodora Maria theodora_manea Data 27 octombrie 2011 09:22:37
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <cstring>

#define max_n 2000001
#define P 73
#define mod1 100007
#define mod2 100021

using namespace std;

char a[max_n],b[max_n];
int na,nb,i,cod1,cod2,h1,h2,x,nr,p1,p2;
int v[max_n];

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

int main () {
    in.getline(a,max_n);
    in.getline(b,max_n);
    na=strlen(a);
    nb=strlen(b);

    p1=p2=1;
    if (na>nb) {
       out << '0' << '\n';
       return 0;
    }

    cod1=cod2=0;
    for (i=0; i<na; i++) {  //hash pt model
        cod1=(cod1*P+a[i])%mod1;
        cod2=(cod2*P+a[i])%mod2;
        if (i) {
            p1=(p1*P)%mod1;
            p2=(p2*P)%mod2;
        }
    }

    h1=h2=0;

    for (i=0; i<na; i++) {  //hash pentru prima bucata din string
         h1=(h1*P+b[i])%mod1;
         h2=(h2*P+b[i])%mod2;
    }

    nr=0;
    if (cod1==h1 && cod2==h2) {
        v[0]=1;
        nr++;
    }

    for (i=na; i<nb; i++) {
        h1=((h1-(b[i-na]*p1)%mod1+mod1)*P+b[i])%mod1;
        h2=((h2-(b[i-na]*p2)%mod2+mod2)*P+b[i])%mod2;
        if (h1==cod1 && h2==cod2) {
            v[i-na+1]=1;
            nr++;
        }
    }

    out << nr << '\n';
    x=0;
    for (i=0; i<nb && x<1000; i++) {
        if (v[i]) {
           out << i << ' ';
           x++;
           }
    }
    return 0;
}