Cod sursa(job #1458217)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 7 iulie 2015 10:04:13
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#include <cstdio>
#include <cstring>
#define MOD1 100021
#define MOD2 100007
#define DIM 2000007
#define base 73
using namespace std;
FILE *fin, *fout;
char A[DIM], B[DIM];
int Na, Nb, ha1, ha2, hb1, hb2, occ[DIM], ct, p1=1, p2=1;
void hashA()
{
    for(int i = 0; i< Na; i++)
    {
        ha1 = ((1LL*ha1*base)%MOD1 + A[i])%MOD1;
        ha2 = ((1LL*ha2*base)%MOD2 + A[i])%MOD2;
        if(i)
        {
            p1 = (p1*base)%MOD1;
            p2 = (p2*base)%MOD2;
        }
    }
}
void hashB()
{
    for(int i = 0; i< Na; i++)
    {
        hb1 = ((1LL*hb1*base)%MOD1 + B[i])%MOD1;
        hb2 = ((1LL*hb2*base)%MOD2 + B[i])%MOD2;
    }
}
int main()
{
    fin = freopen("strmatch.in", "r", stdin);
    fout = freopen("strmatch.out", "w", stdout);
    scanf("%s", A);
    scanf("%s", B);
    Na = strlen(A);
    Nb = strlen(B);
    if(Na > Nb)
    {
        printf("0\n");
        fclose(fin);
        fclose(fout);
        return 0;
    }
    hashA();
    hashB();
    if(ha1 == hb1 && ha2 == hb2)
    {
        occ[ct] = 0;
        ct++;
    }
    for(int i = Na; i< Nb; i++)
    {
        hb1 = ((hb1 - (1LL*p1*B[i-Na])%MOD1 + MOD1)*base + B[i])%MOD1;
        hb2 = ((hb2 - (1LL*p2*B[i-Na])%MOD2 + MOD2)*base + B[i])%MOD2;
        if(ha1 == hb1 && ha2 == hb2)
        {
            occ[ct] = i-Na+1;
            ct++;
        }
    }
    if(ct <= 1000)
    {
        printf("%d\n", ct);
        for(int i = 0; i< ct; i++) printf("%d ", occ[i]);
        printf("\n");
    }
    else
    {
        printf("%d\n", ct);
        for(int i = 0; i< 1000; i++) printf("%d ", occ[i]);
        printf("\n");
    }
    fclose(fin);
    fclose(fout);
    return 0;
}