Cod sursa(job #3363203)

Utilizator CorvinJudge0Corvin Judge CorvinJudge0 Data 14 august 2026 12:41:03
Problema Potrivirea sirurilor Scor 40
Compilator c-64 Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <stdio.h>

#define MAXN 2000000
#define MAXK 1000

int mod[2] = {1000000007, 1000000009}, b[2] = {67, 71}, putere[2];
int inv[MAXN + 1][2], h[MAXN + 1][2], rasp[MAXK + 1], hash[2];

int exp(int a, int n, int m) {
    int t;
    if (n == 0) {
        return 1;
    } else {
        if (n % 2 == 1) {
            return ((long long)a * exp(a, n - 1, m)) % mod[m];
        } else {
            t = exp(a, n / 2, m);
            return ((long long)t * t) % mod[m];
        }
    }
}

static inline int conv(int ch) {
    if ('a' <= ch && ch <= 'z') {
        return ch - 'a' + 1;
    } else if ('A' <= ch && ch <= 'Z') {
        return ch - 'A' + 27;
    } else if ('0' <= ch && ch <= '9') {
        return ch - '0' + 53;
    } else {
        return 0;
    }
}

static inline int get(int a, int b, int m) {
    return ((long long)((h[b][m] - h[a - 1][m] + mod[m]) % mod[m]) * inv[a - 1][m]) % mod[m];
}

signed main() {
    FILE *fin, *fout;
    int n, m, k, ch, i, j;

    for (i = 0; i < 2; i++) {
        inv[MAXN][i] = exp(exp(b[i], MAXN, i), mod[i] - 2, i);
    }
    for (i = MAXN - 1; i >= 0; i--) {
        for (j = 0; j < 2; j++) {
            inv[i][j] = ((long long)inv[i + 1][j] * b[j]) % mod[j];
        }
    }

    fin = fopen("strmatch.in", "r");
    n = 0;
    putere[0] = putere[1] = 1;
    while ((ch = fgetc(fin)) != '\n') {
        n++;
        for (i = 0; i < 2; i++) {
            hash[i] = (hash[i] + ((long long)conv(ch) * putere[i]) % mod[i]) % mod[i];
            putere[i] = ((long long)putere[i] * b[i]) % mod[i];
        }
    }

    m = 0;
    putere[0] = putere[1] = 1;
    while ((ch = fgetc(fin)) != '\n' && ch != EOF) {
        m++;
        for (i = 0; i < 2; i++) {
            h[m][i] = (h[m - 1][i] + ((long long)conv(ch) * putere[i]) % mod[i]) % mod[i];
            putere[i] = ((long long)putere[i] * b[i]) % mod[i];
        }
    }
    fclose(fin);

    k = 0;
    i = 1;
    while (i <= m - n + 1 && k <= MAXK) {
        if (get(i, i + n - 1, 0) == hash[0] && get(i, i + n - 1, 1) == hash[1]) {
            rasp[++k] = i;
        }
        i++;
    }

    fout = fopen("strmatch.out", "w");
    fprintf(fout, "%d\n", k);
    for (i = 1; i <= k; i++) {
        fprintf(fout, "%d ", rasp[i] - 1);
    }
    fclose(fout);

    return 0;
}