Cod sursa(job #1526847)

Utilizator dragomir_ioanDragomir Ioan dragomir_ioan Data 17 noiembrie 2015 15:14:47
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include<cstdio>
#include<string.h>

#define baza 127
#define mod1 100007
#define mod2 100021

#define strl 2000001

char a[strl], b[strl], o[5001];

int hashA1, hashA2, hashB1, hashB2;
long long p1, p2;

char pot[strl];
int nrpot;

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

    scanf("%s%s", a, b);
    int la = strlen(a), lb = strlen(b);

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

    int i;
    p1 = p2 = 1;
    for(i=0; i<la; i++) {
        hashA1 = (hashA1 * baza + a[i]) % mod1;//Calcules hash-urile sirului A
        hashA2 = (hashA2 * baza + a[i]) % mod2;

        hashB1 = (hashB1 * baza + b[i]) % mod1;//Calcules hash-urile primei parti a sirului B A
        hashB2 = (hashB2 * baza + b[i]) % mod2;

        if(i!=0)
            p1 = (p1 * baza) % mod1,
            p2 = (p2 * baza) % mod2;
    }

    if(hashB1 == hashA1 && hashB2 == hashA2) pot[0] = 1, nrpot = 1;

    for(i=la; i<lb; i++) {
        if(hashB1 == hashA1 && hashB2 == hashA2) pot[i-la] = 1, nrpot++;

        hashB1 = ((hashB1 - (b[i-la] * p1) % mod1 + mod1) * baza + b[i]) % mod1;
        hashB2 = ((hashB2 - (b[i-la] * p2) % mod2 + mod2) * baza + b[i]) % mod2;
    }
    printf("%d\n", nrpot);

    nrpot = 0;
    for (int i = 0; i < lb && nrpot < 1000; i++)
        if (pot[i])
            nrpot++,
            printf("%d ", i);

    return 0;
}