Cod sursa(job #3365871)

Utilizator TianaInfoLitcanu Tiana TianaInfo Data 27 septembrie 2026 10:55:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
//KMP
#include <bits/stdc++.h>
using namespace std;

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

#define cin fin
#define cout fout

int n,m,i,j,nr,pi[2000005],rez[1005];
string a,b;

int main()
{


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

    j=0;
    for(i=1; i<n; i++)
    {
        while(j>0 && a[i]!=a[j]) j=pi[j-1];
        if(a[i]==a[j]) j++;
        pi[i]=j;
    }

    j=0;
    nr=0;
    for(i=0; i<m; i++)
    {
        while(j>0 && b[i]!=a[j]) j=pi[j-1];
        if(b[i]==a[j]) j++;

        if(j==n)
        {
            nr++;
            if(nr<=1000) rez[nr]=i-n+1;
            j=pi[j-1];
        }
    }

    cout<<nr<<'\n';
    for(i=1; i<=min(nr,1000); i++)
        cout<<rez[i]<<' ';

    return 0;
}