Cod sursa(job #3330344)

Utilizator RZV139fjDragomir Ioan Razvan RZV139fj Data 18 decembrie 2025 19:47:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char p[2000005];
char t[2000005];
int f[2000005];
int rezolv[1003];

int main()
{
    fin>>p>>t;
    f[0]=0;
    int m=strlen(p);
    int k=0,cnt=0;
    for(int q=1; q<m; q++)
    {
        while(k>0&&p[k]!=p[q])
        {
            k=f[k-1];
        }
        if(p[k]==p[q]) k++;
        f[q]=k;
    }

    int q=0;
    int n=strlen(t);

    for(int i=0; i<n; i++)
    {
        while(q>0&&p[q]!=t[i])
        {
            q=f[q-1];
        }
        if(p[q]==t[i])
        {
            q++;
        }
        if(q==m)
        {
            cnt++;
            if(cnt<=1000) rezolv[cnt]=i-m+1;
            q=f[q-1];
        }
    }

    fout<<cnt<<endl;
    for(int i=1; i<=min(1000,cnt); i++)
    {
        fout<<rezolv[i]<<' ';
    }

    return 0;
}