Cod sursa(job #1816044)

Utilizator silkMarin Dragos silk Data 26 noiembrie 2016 00:46:15
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <cstdio>
#include <cstring>
#define LMax 2000005
#define NMax 1000

const int P = 147481;
const int Q = 4733;

int rez[NMax+1];
char A[LMax+1];
char B[LMax+1];

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

    int i,lgA,lgB,a,b,pwrP,pwrQ,u,v,nr;

    fgets(A,LMax-1,stdin);
    lgA = strlen(A)-1;

    fgets(B,LMax-1,stdin);
    lgB = strlen(B);
    if( B[lgB-1] == '\n' ) --lgB;

    if( lgB<lgA ) { printf("0\n"); return 0; }

    for(pwrP = pwrQ = i = 1; i < lgA; ++i)
    {
        pwrP = ( pwrP * 47 ) % P;
        pwrQ = ( pwrQ * 47 ) % Q;
    }

    for(a = b = 0, i = 1; i <= lgA; ++i)
    {
        a = ( a*47 + A[i-1] ) % P;
        b = ( b*47 + A[i-1] ) % Q;
    }

    for(u = v = nr = 0, i = 1; i <= lgA; ++i)
    {
        u = ( u*47 + B[i-1] ) % P;
        v = ( v*47 + B[i-1] ) % Q;
    }

    if( u==a&&v==b ) rez[++nr] = 1;

    for(i = lgA+1; i <= lgB; ++i)
    {
        u = ( ( ( u - B[i-lgA-1] * pwrP + 256 * P ) % P ) * 47 + B[i-1] ) % P;
        v = ( ( ( v - B[i-lgA-1] * pwrQ + 256 * Q ) % Q ) * 47 + B[i-1] ) % Q;

        if( u==a&&v==b )
        {
            if(nr<NMax) rez[++nr] = i-lgA;
            else ++nr;
        }
    }

    printf("%d\n",nr);
    for(i = 1; i <= nr; ++i) printf("%d ",rez[i]);



return 0;
}