Cod sursa(job #3365872)

Utilizator TianaInfoLitcanu Tiana TianaInfo Data 27 septembrie 2026 11:09:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
//Z-function
#include <bits/stdc++.h>
using namespace std;

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

#define cin fin
#define cout fout

int n,m,l,r,i,j,nr,z[4000005];
string a,b,s;

int main()
{
    cin>>a>>b;

    n=a.size();
    m=b.size();

    s=a+'#'+b;

    l=0;
    r=0;
    nr=0;

    for(i=1;i<s.size();i++)
    {
        if(i<=r)
            z[i]=min(r-i+1,z[i-l]);

        while(i+z[i]<s.size() && s[z[i]]==s[i+z[i]])
            z[i]++;

        if(i+z[i]-1>r)
        {
            l=i;
            r=i+z[i]-1;
        }

        if(z[i]>=n)
            nr++;
    }

    cout<<nr<<'\n';

    j=0;

    for(i=n+1;i<s.size() && j<1000;i++)
    {
        if(z[i]>=n)
        {
            cout<<i-n-1<<' ';
            j++;
        }
    }

    return 0;
}