Cod sursa(job #3321444)

Utilizator mbazacliuMihnea Gabriel Bazacliu mbazacliu Data 9 noiembrie 2025 15:25:40
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>
using namespace std;

#define M0 4000000007ll
#define M1 4000000009ll
#define B0 131ll
#define B1 149ll

typedef unsigned int       ui;
typedef unsigned long long ul;

ifstream I("strmatch.in");
ofstream O("strmatch.out");

int main(){
    string s, t;
    I >> s >> t;

    int m = s.length(), n = t.length();
    int l = 0, a[1000];
    set<unsigned long long> x;
    unsigned long long xh[2] = {};

    for (int i = 0; i < m; i++){
        xh[0] = (xh[0] * B0 + s[i]) % M0;
        xh[1] = (xh[1] * B1 + s[i]) % M1;
    }

    x.insert((xh[0] * 1ull << 32) + xh[1]);

    {
        ui h[2] = {}, p[2] = {1, 1};

        for (int i = 0; i < m; i++){
            h[0] = (h[0] * B0 + t[i]) % M0;
            h[1] = (h[1] * B1 + t[i]) % M1;
        }

        for (int k = 1; k < m; k++){
            p[0] = p[0] * B0 % M0;
            p[1] = p[1] * B1 % M1;
        }

        for (int i = 0; i <= n-m; i++){
            if (x.contains((h[0] * 1ull << 32) + h[1])){
                if (l < 1000) a[l] = i;
                l++;
            }

            if (i < n-m){
                h[0] = ((h[0] + M0 - 1ll * p[0] * t[i] % M0) * B0 + t[i+m]) % M0;
                h[1] = ((h[1] + M1 - 1ll * p[1] * t[i] % M1) * B1 + t[i+m]) % M1;
            }
        }
    }

    O << l << '\n';
    for (int i = 0; i < l && i < 1000; i++) O << a[i] << ' ';
}