Cod sursa(job #3348089)

Utilizator stefan_ciureaStefan Ciurea stefan_ciurea Data 19 martie 2026 17:09:33
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <bits/stdc++.h>

using namespace std;

const int Nmax=4e6+5;

int z[Nmax],n;

void z_algo(string s) {
    int l=0,r=0;
    for (int i=1; i<n; ++i) {
        if (i<r) z[i]=min(r-i,z[i-l]);
        while (i+z[i]<n && s[z[i]]==s[i+z[i]]) z[i]++;
        if (i+z[i]>r) {
            r=i+z[i];
            l=i;
        }
    }
}

int main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    string a,b;
    cin>>a>>b;
    string s=a+"$"+b;
    n=s.size();
    z_algo(s);
    int m=a.size(),lim=1000;
    vector<int> ans;
    for (int i=m+1; i<n; ++i) {
        if (z[i]==m) ans.push_back(i-m-1);
    }
    cout<<ans.size()<<'\n';
    for (int i=0; i<ans.size() && lim; --lim,++i) cout<<ans[i]<<' ';
    cin.close();
    cout.close();
    return 0;
}