Cod sursa(job #3209388)

Utilizator Sabin1133Padurariu Sabin Sabin1133 Data 2 martie 2024 12:09:59
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <bits/stdc++.h>

#define NMAX 2000001
#define MAXCOUNT 1000

#define P 73
#define MOD1 100007
#define MOD2 100021

char A[NMAX];
char B[NMAX];
char match[NMAX];

int main()
{
    int nr = 0;
    int lenA, lenB;
    int P1, P2;
    int hashA1, hashA2;
    int hashB1, hashB2;

    std::ifstream fin("strmatch.in");
    std::ofstream fout("strmatch.out");

    fin >> A >> B;

    fin.close();

    lenA = strlen(A);
    lenB = strlen(B);

    if (lenA > lenB) {
        fout << nr << '\n';
        fout.close();
    }

    for (int i = 0; i < lenA; ++i) {
        hashA1 = (hashA1 * P + A[i]) % MOD1;
        hashA2 = (hashA2 * P + A[i]) % MOD2;

        if (i > 0) {
            P1 = (P1 * P) % MOD1;
            P2 = (P2 * P) % MOD2;
        }
    }

    for (int i = 0; i < lenA; ++i) {
        hashB1 = (hashB1 * P + B[i]) % MOD1;
        hashB2 = (hashB2 * P + B[i]) % MOD2;
    }

    if (hashA1 == hashB1 && hashA2 == hashB2) {
        match[0] = 1;
        ++nr;
    }

    for (int i = lenA; i < lenB; ++i) {
        hashB1 = ((hashB1 - (B[i - lenA] * P1) % MOD1 + MOD1) * P + B[i]) % MOD1;
        hashB2 = ((hashB2 - (B[i - lenA] * P2) % MOD2 + MOD2) * P + B[i]) % MOD2;

        if (hashA1 == hashB1 && hashA2 == hashB2) {
            match[i - lenA + 1] = 1;
            ++nr;
        }
    }

    fout << nr << '\n';

    nr = 0;
    for (int i = 0; i < lenB && nr < MAXCOUNT; ++i)
        if (match[i]) {
            ++nr;
            fout << i << ' ';
        }
    
    fout << '\n';

    fout.close();

    return 0;
}