Cod sursa(job #3370836)

Utilizator Nicholas123Tudose Nicholas Nicholas123 Data 27 octombrie 2026 14:22:26
Problema Potrivirea sirurilor Scor 92
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <cstring>
using namespace std;

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

const int N = 2000005;
const long long MOD = 1000000007;
const long long P = 31;

char A[N], B[N];
long long pref[N], pw[N];
int poz[1005];

int n, m, cnt;

long long getHash(int l, int r) {
    return (pref[r] - pref[l] * pw[r - l] % MOD + MOD) % MOD;
}

int main() {
    fin >> A >> B;

    n = strlen(A);
    m = strlen(B);

    pw[0] = 1;
    for (int i = 1; i <= m; i++)
        pw[i] = pw[i - 1] * P % MOD;

    for (int i = 0; i < m; i++)
        pref[i + 1] = (pref[i] * P + B[i] - 'A' + 1) % MOD;

    long long hashA = 0;
    for (int i = 0; i < n; i++)
        hashA = (hashA * P + A[i] - 'A' + 1) % MOD;

    for (int i = 0; i + n <= m; i++) {
        if (getHash(i, i + n) == hashA) {
            if (cnt < 1000)
                poz[cnt] = i;
            cnt++;
        }
    }

    fout << cnt << '\n';

    for (int i = 0; i < min(cnt, 1000); i++)
        fout << poz[i] << ' ';

    fout << '\n';

    return 0;
}