Cod sursa(job #1575959)

Utilizator valentinpielePiele Valentin valentinpiele Data 21 ianuarie 2016 22:45:59
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include <cstdio>
#include <cstring>
#define B1 27
#define B2 29
#define MOD1 10007
#define MOD2 666013

using namespace std;

char X[2000020],Y[2000020];
int match[2000020],v1,v2,h1,h2,n,m,p1,p2,i,nr;


int main()
{
    freopen ("strmatch.in","r",stdin);
    freopen ("strmatch.out","w",stdout);
    scanf ("%s",X);
    scanf ("%s",Y);

    m = strlen(X);
    n = strlen(Y);

    if ( m > n )
    {
        printf ("0\n");
        return 0;
    }

    p1=p2=1;
    v1=v2=0;

    // se calculeaza valoarea sirului X
    for (i=0; i<m; i++)
    {
        v1 = ( v1 * B1 + X[i]) % MOD1;
        v2 = ( v2 * B2 + X[i]) % MOD2;

        // se precalculeaza puterea la care un element va fi scos din sablon
        if ( i!=1 )
        {
            p1 = ( p1 * B1 ) % MOD1;
            p2 = ( p2 * B2 ) % MOD2;
        }
    }

    h1=h2=0;

    // se calculeaza valoarea primei subsecvente din Y
   for (i=0; i<m; i++)
    {
        h1 = ( h1 * B1 + Y[i]) % MOD1;
        h2 = ( h2 * B2 + Y[i]) % MOD2;
    }

    // se verifica daca valorile primei subsecvente coincid cu sablonul
    if (h1 == v1 && h2 == v2)
    {
        nr++;
        match[0] = 1;
    }

    // se contunua pana la finalul sirului X
    for (i=m; i<n; i++)
    {
        h1 = ((h1 - (Y[i - m] * p1) % MOD1 + MOD1) * B1 + Y[i] ) % MOD1;
        h2 = ((h2 - (Y[i - m] * p2) % MOD2 + MOD2) * B2 + Y[i] ) % MOD2;
        if (h1 == v1 && h2 == v2)
        {
            nr++;
            match[i - m +1] = 1;
        }
    }

    printf ("%d\n",nr);

    for (i = 0; i < n; i++)
       if (match[i])
            printf("%d ", i);
       printf("\n");
    return 0;
}