Cod sursa(job #3321406)

Utilizator mbazacliuMihnea Gabriel Bazacliu mbazacliu Data 9 noiembrie 2025 13:19:18
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>
using namespace std;

#define M0 3666666677ll
#define M1 4294967291ll
#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();

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

    for (int i = 0; i < m; i++){
        x[0] = (x[0] * B0 + s[i]) % M0;
        x[1] = (x[1] * B1 + s[i]) % M1;
        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;
    }

    int l = 0, a[1000];
    for (int i = 0; i <= n-m; i++){

        if (h[0] == x[0] && h[1] == x[1]){
            bool g = 1;
            for (int j = 0; j < m; j++){
                if (t[i + j] != s[j]){
                    g = 0;
                    break;
                }
            }
            if (g){
                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] << ' ';
}