Cod sursa(job #3363197)

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

#define int long long

#define MAXN 2000000
#define MAXK 1000
#define MOD 1000000007
#define B 113

int inv[MAXN + 1], h[MAXN + 1], rasp[MAXK + 1];

int exp(int a, int n) {
    int t;
    if (n == 0) {
        return 1;
    } else {
        if (n % 2 == 1) {
            return (a * exp(a, n - 1)) % MOD;
        } else {
            t = exp(a, n / 2);
            return (t * t) % MOD;
        }
    }
}

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) {
    return (((h[b] - h[a - 1] + MOD) % MOD) * inv[a - 1]) % MOD;
}

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

    inv[MAXN] = exp(exp(B, MAXN), MOD - 2);
    for (i = MAXN - 1; i >= 0; i--) {
        inv[i] = (inv[i + 1] * B) % MOD;
    }

    fin = fopen("strmatch.in", "r");
    n = hash = 0;
    pow = 1;
    while ((ch = fgetc(fin)) != '\n') {
        n++;
        hash = (hash + conv(ch) * pow) % MOD;
        pow = (pow * B) % MOD;
    }

    m = 0;
    pow = 1;
    while ((ch = fgetc(fin)) != '\n' && ch != EOF) {
        m++;
        h[m] = (h[m - 1] + conv(ch) * pow) % MOD;
        pow = (pow * B) % MOD;
    }
    fclose(fin);

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

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

    return 0;
}