Cod sursa(job #3333850)

Utilizator snelvladSnel Vlad snelvlad Data 15 ianuarie 2026 14:20:21
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <iostream>
#include <fstream>
#include <map>
#include <vector>
#include <cstring>

using namespace std;

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

char a1[2000001], b1[2000001];
int a[2000001], b[2000001], pp[2000001], s[2000001];

int main(){

    int n, m, i, p=1327, mod=10663, sa, sb, nr=0, poz[1000];
    f >> a1 >> b1;
    m=strlen(a1); n=strlen(b1);
    //cout << n << '\n';
    for(i=0; i<m; i++){
        //cout << a1[i];
    }
    //cout << '\n' << m << '\n';
    for(i=0; i<n; i++){
        //cout << b1[i];
        a[i] = b1[i];
    }
    //cout << '\n';
    for(i=1; i<=m; i++){
        b[i] = a1[i-1];
        //cout << b[i] << " ";
    }
    //cout << '\n';
    for(i=1; i<=n; i++){
        a[i] = b1[i-1];
        //cout << a[i] << " ";
    }

    pp[0]=1;
    for(i=1; i<=m; i++)
        pp[i]=(pp[i-1]*p)%mod;
    pp[1]=a[1];
    for(i=2; i<=n; i++)
        s[i]=(s[i-1]*p+a[i])%mod;
    sb=b[1];
    for(i=2; i<=m; i++)
        sb=(sb*p+b[i])%mod;
    for(i=1; i<=n-m+1; i++){
        sa=((s[i+m-1]-s[i-1]*pp[m])%mod+mod)%mod;
        if(sa==sb){
            nr++;
            if(poz[nr]==0)poz[nr]=i-1;
        }
    }
    if(nr>0){
        cout << nr << '\n';
        for(i=1; i<=nr; i++){
            cout << poz[i] << " ";
        }
    }
    else cout << "NU";


    f.close();
    g.close();
    return 0;
}