Cod sursa(job #3305260)

Utilizator InformaticianInDevenire1Munteanu Mihnea Gabriel InformaticianInDevenire1 Data 31 iulie 2025 09:34:26
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

int Z[4000005];
vector <int> pos;

void buildZ(string &a){
    Z[0] = 0;
    int best = 0;
    for (int i=1;i<a.length();i++){
        if (i<=best+Z[best]-1){
            Z[i] = min(best+Z[best]-i,Z[i-best]);
        }
        while (a[i+Z[i]]==a[Z[i]]){
            Z[i]++;
        }
        if (best+Z[best]<i+Z[i]){
            best = i;
        }
    }
    return;
}


signed main()
{
    string a,b;
    fin >> a >> b;
    int cnt = 0;
    int targetSize = a.size();
    a += '$';
    a += b;
    buildZ(a);
    for (int i=0;i<a.size();i++){
        if (Z[i]==targetSize){
            cnt++;
            if (pos.size()==1000) continue;
            pos.push_back(i-targetSize-1);
        }
    }
    fout << cnt << '\n';
    for (auto x:pos){
        fout << x << ' ';
    }
}