Cod sursa(job #1008756)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 11 octombrie 2013 19:33:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <cstdio>
#include <cstring>

using namespace std;

const int Nmax = 2000005;
const int M1 = 100007;
const int M2 = 100021;
const int base = 73;

char a[ Nmax ] , b[ Nmax ] , match [ Nmax ];
int hashA1,hashA2,hash1,hash2,p1=1,p2=1,nr;
int lena,lenb,gata;

void solve()
{
    lena=strlen(a),lenb=strlen(b);
    for(int i = 0; i < lena ; ++i){
            hashA1 = (hashA1*base + a[i])%M1,
            hashA2 = (hashA2*base + a[i])%M2;
        if(i)
            p1 = (p1 * base) % M1,// aici imi retin de cate
            p2 = (p2 * base) % M2;//ori am inmultit primul element
    }
    if( lena  > lenb ){
        printf("0\n");
        gata = 1;
        return;
    }

    for(int i = 0 ;i < lena; ++i)
        hash1 = ( hash1*base + b[i]) % M1,
        hash2 = ( hash2*base + b[i]) % M2;

    if ( hashA1==hash1 && hashA2==hash2 )
        match [ 0 ] = 1, ++nr;

    for(int i = lena ; i < lenb ; ++i)
    {
        // scot din hashuri pe b[ i - lena]
        hash1 = (hash1 - (b[i-lena]*p1)%M1 + M1);
        hash2 = (hash2 - (b[i-lena]*p2)%M2 + M2);
        // bag in hashuri pe b[i]
        hash1 = (hash1*base + b[i])%M1;
        hash2 = (hash2*base + b[i])%M2;
        // daca corespund hashurile avem solutie
        if(hashA1==hash1 && hashA2==hash2)
            match[i-lena+1] = 1,++nr;
    }
}

void afish()
{
    if(gata) return;
    int prints = 0;
    printf("%d\n",nr);
    for(int i = 0; i<lenb && prints<1000; ++i )
        if(match[i])
            printf("%d ",i),++prints;
}

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);

    scanf("%s\n%s",&a,&b);
    solve();
    afish();
    return 0;
}