Cod sursa(job #3321355)

Utilizator mbazacliuMihnea Gabriel Bazacliu mbazacliu Data 9 noiembrie 2025 12:04:46
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>
using namespace std;

#define M0 3666666677ll
#define B0 131ll

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[1] = {}, x[1] = {}, p[1] = {1};

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

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

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

        if (h[0] == x[0]){
            bool g = 1;
            int  j = 0;
            for (char c : s){
                if (t[i + j] != c){
                    g = 0;
                    break;
                }
                j++;
            }
            if (g){
                if (l < 1000) a[l] = i;
                l++;
            }
        }

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

    O << l << '\n';

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