Cod sursa(job #1274781)

Utilizator HotSteelBeteag Ion Andrei HotSteel Data 24 noiembrie 2014 12:10:26
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <cstdio>
#include <cstring>

#define K0 73
#define K1 100007
#define K2 100021

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

    char *A = new char[2000005];
    char *B = new char[2000005];

    scanf("%s %s", A, B);

    int LenA, LenB;
    LenA = strlen(A);
    LenB = strlen(B);

    if(LenA > LenB)
    {
        printf("0");
        return 0;
    }

    int HashA1, HashA2;
    int Hash1, Hash2;
    int P1, P2;

    HashA1 = HashA2 = Hash1 = Hash2 = 0;
    P1 = P2 = 1;

    HashA1 = (HashA1 * K0 + A[0]) % K1;
    HashA2 = (HashA2 * K0 + A[0]) % K2;

    int i;
    for(i = 1 ; i < LenA ; ++i)
    {
        HashA1 = (HashA1 * K0 + A[i]) % K1;
        HashA2 = (HashA2 * K0 + A[i]) % K2;

        P1 = (P1 * K0) % K1;
        P2 = (P2 * K0) % K2;
    }

    for(i = 0 ; i < LenA ; ++i)
    {
        Hash1 = (Hash1 * K0 + B[i]) % K1;
        Hash2 = (Hash2 * K0 + B[i]) % K2;
    }

    int Count = 0;
    int *Matches = new int[2000005];

    if(HashA1 == Hash1 && HashA2 == Hash2)
        Matches[++Count] = 1;

    for(i = LenA ; i < LenB ; ++i)
    {
        Hash1 = ((Hash1 - (B[i - LenA] * P1) % K1 + K1) * K0 + B[i]) % K1;
        Hash2 = ((Hash2 - (B[i - LenA] * P2) % K2 + K2) * K0 + B[i]) % K2;

        if(Hash1 == HashA1 && Hash2 == HashA2)
            Matches[++Count] = i - LenA + 1;
    }

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

    delete[] A;
    delete[] B;
    delete[] Matches;

    return 0;
}