Cod sursa(job #1167123)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 4 aprilie 2014 13:28:14
Problema Potrivirea sirurilor Scor 78
Compilator cpp Status done
Runda Arhiva educationala Marime 2.02 kb
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int LMAX = 2000000+5;
const int MOD1 = 100007;
const int MOD2 = 100009;
const int MOD3 = 666013;
const int BASE = 'z' + 1;

void Read(),Solve(),Print();

int LA,LB,Nr_Potriviri;
char A[LMAX];
char B[LMAX];
int Potriviri[1005];
int B1,B2,B3;
int Hash1_A,Hash2_A,Hash3_A;
int Hash1_B,Hash2_B,Hash3_B;

int main()
{
    Read();
    Solve();
    Print();

    return 0;
}

void Read()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);

    scanf("%s",A+1);
    scanf("%s",B+1);
}

void Solve()
{
    int i;

    LA = strlen(A+1);
    LB = strlen(B+1);

    B1 = B2 = B3 = 1;

    for(i = 1; i <= LA; i++)
    {
        Hash1_A = (Hash1_A * BASE + A[i])%MOD1;
        Hash2_A = (Hash2_A * BASE + A[i])%MOD2;
        Hash3_A = (Hash3_A * BASE + A[i])%MOD3;

        if(i >= 2) B1 = (B1 * BASE)%MOD1;
        if(i >= 2) B2 = (B2 * BASE)%MOD2;
        if(i >= 2) B3 = (B3 * BASE)%MOD3;

        Hash1_B = (Hash1_B * BASE + B[i])%MOD1;
        Hash2_B = (Hash2_B * BASE + B[i])%MOD2;
        Hash3_B = (Hash3_B * BASE + B[i])%MOD3;
    }

    if(Hash1_A == Hash1_B && Hash2_A == Hash2_B && Hash3_A == Hash3_B)
    {
        Nr_Potriviri++;
        if(Nr_Potriviri <= 1000) Potriviri[Nr_Potriviri] = i - LA;
    }

    for(; i <= LB; i++)
    {
        Hash1_B = ((((Hash1_B - (B1 * B[i-LA])% MOD1) * BASE)% MOD1) + MOD1 + B[i])%MOD1;
        Hash2_B = ((((Hash2_B - (B2 * B[i-LA])% MOD2) * BASE)% MOD2) + MOD2 + B[i])%MOD2;
        Hash3_B = ((((Hash3_B - (B3 * B[i-LA])% MOD3) * BASE)% MOD3) + MOD3 + B[i])%MOD3;

        if(Hash1_A == Hash1_B && Hash2_A == Hash2_B && Hash3_A == Hash3_B)
        {
            Nr_Potriviri++;
            if(Nr_Potriviri <= 1000) Potriviri[Nr_Potriviri] = i - LA;
        }
    }
}

void Print()
{
    int i;

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

    for(i = 1; i <= min(1000,Nr_Potriviri); i++)
        printf("%d ",Potriviri[i]);
}