Cod sursa(job #1458209)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 7 iulie 2015 09:55:29
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 2.1 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, tmp1, tmp2;
int power1(int a, int b)
{
    int sol = 1;
    for(; b; b>>=1)
    {
        if(b&1)
        {
            sol = (1LL*sol*a)%MOD1;
        }
        a=(1LL*a*a)%MOD1;
    }
    return sol;
}
int power2(int a, int b)
{
    int sol = 1;
    for(; b; b>>=1)
    {
        if(b&1)
        {
            sol = (1LL*sol*a)%MOD2;
        }
        a=(1LL*a*a)%MOD2;
    }
    return sol;
}
void hashA()
{
    for(int i = 0; i< Na; i++)
    {
        ha1 = ((1LL*ha1*base)%MOD1 + (int)A[i])%MOD1;
        ha2 = ((1LL*ha2*base)%MOD2 + (int)A[i])%MOD2;
    }
}
void hashB()
{
    for(int i = 0; i< Na; i++)
    {
        hb1 = ((1LL*hb1*base)%MOD1 + (int)B[i])%MOD1;
        hb2 = ((1LL*hb2*base)%MOD2 + (int)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++;
    }
    tmp1 = power1(base, Na-1);
    tmp2 = power2(base, Na-1);
    for(int i = Na; i<= Nb; i++)
    {
        hb1 = ((hb1 - (1LL*tmp1*B[i-Na])%MOD1 + MOD1)*base + (int)B[i])%MOD1;
        hb2 = ((hb2 - (1LL*tmp2*B[i-Na])%MOD2 + MOD2)*base + (int)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;
}