Cod sursa(job #3200413)

Utilizator Mihai_PopescuMihai Popescu Mihai_Popescu Data 4 februarie 2024 16:46:45
Problema Potrivirea sirurilor Scor 78
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <fstream>
#include <cstring>
using namespace std;

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

#define NMAX 2000005

#define MOD1 100007
#define MOD2 100021

#define b1 101
#define b2 103

char a[NMAX], b[NMAX];
int rez[1005];

int main() {
    fin >> a >> b;
    int l1 = strlen(a), l2 = strlen(b);

    if (l1 > l2) {
        fout << 0;
        return 0;
    }

    int h1 = 0, h2 = 0;
    for (int i = 0; i < l1; ++i) {
        h1 = (h1 * b1 + a[i]) % MOD1;
        h2 = (h2 * b2 + a[i]) % MOD2;
    }

    int hash1 = 0, hash2 = 0;
    int putere1 = 1, putere2 = 1;
    for (int i = 0; i < l1; ++i) {
        hash1 = (hash1 * b1 + b[i]) % MOD1;
        hash2 = (hash2 * b2 + b[i]) % MOD2;
        if (i != 0) {
            putere1 *= b1;
            putere2 *= b2;

            putere1 %= MOD1;
            putere2 %= MOD2;
        }
    }
    int nr = 0;
    int cnt = 0;
    if (h1 == hash1 && h2 == hash2) {
        rez[++cnt] = 0;
    }
    for (int i = l1; i < l2; ++i) {
        hash1 = ((hash1 - b[i - l1] * putere1 % MOD1 + MOD1) % MOD1 * b1 % MOD1 + b[i]) % MOD1;
        hash2 = ((hash2 - b[i - l1] * putere2 % MOD2 + MOD2) % MOD2 * b2 % MOD2 + b[i]) % MOD2;

        if (h1 == hash1 && h2 == hash2) {
            nr++;
            if (cnt < 1000) {
                rez[++cnt] = i - l1 + 1;
            }
        }
    }

    fout << nr << '\n';
    for (int i = 1; i <= cnt; ++i) {
        fout << rez[i] << ' ';
    }
    return 0;
}