Cod sursa(job #3321348)

Utilizator mbazacliuMihnea Gabriel Bazacliu mbazacliu Data 9 noiembrie 2025 11:51:07
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 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;

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

    for (char c : s){
        x[0] = (x[0] * B0 + c) % M0;
    }

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

    int i = 1, m = s.length(), l = 0, a[1000];
    for (char c : t){
        h[0] = (h[0] * B0 + c) % M0;

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

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

    O << l << '\n';

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