Cod sursa(job #3333360)

Utilizator m.at.eiDabu Matei m.at.ei Data 13 ianuarie 2026 10:36:52
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>
using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

const int MAXN = 1000005;
const long long MOD = 998244353;
const long long P = 1000000007;

char text[MAXN], pat[MAXN];
long long htext[MAXN], hpat, pw[MAXN];
int pos[MAXN];

int main()
{
    f.getline(pat, MAXN);
    f.getline(text, MAXN);

    int m = strlen(pat);
    int n = strlen(text);

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

    // hash pattern
    hpat = 0;
    for (int i = 0; i < m; i++)
        hpat = (hpat * P + pat[i]) % MOD;

    // hash text
    htext[0] = 0;
    for (int i = 0; i < n; i++)
        htext[i + 1] = (htext[i] * P + text[i]) % MOD;

    int cnt = 0;
    for (int i = 0; i + m <= n; i++)
    {
        long long cur =
            (htext[i + m] - htext[i] * pw[m] % MOD + MOD) % MOD;

        if (cur == hpat)
            pos[cnt++] = i;
    }

    g << cnt << "\n";
    for (int i = 0; i < min(cnt, 1000); i++)
        g << pos[i] << " ";

    return 0;
}