Cod sursa(job #3300526)

Utilizator raileanu-alin-gabrielRaileanu Alin-Gabriel raileanu-alin-gabriel Data 16 iunie 2025 22:02:25
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#include <cstring>

using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

const int NMAX=2*1e6+5;
int f[NMAX];
char p[NMAX], t[NMAX];

void pref(char * p, int m)
{
    int i, k;
    f[0]=-1;
    for(i=1; i<=m; i++)
    {
        k=f[i-1];
        while(k>=0 && p[k]!=p[i-1]) k=f[k];
        f[i]=k+1;
    }
}

void kmp(char * t, int n, char * p, int m)
{
    int cnt=0, i=0, k=0;
    int ans[1005];
    while(i<=(n-m+1))
    {
        if(t[i+k]==p[k]) k++;
        else if(k==0) i++;
        else
        {
            i+=k-f[k];
            k=f[k];
        }
        if(k==m)
        {
            cnt++;
            if(cnt<=1000) ans[cnt]=i;
        }
    }
    cout<<cnt<<'\n';
    for(i=1; i<=min(cnt, 1000); i++) cout<<ans[i]<<' ';
}

int main()
{
    cin>>p;
    cin>>t;
    int lgp=strlen(p);
    pref(p, lgp);
    kmp(t, strlen(t), p, lgp);
    return 0;
}