Cod sursa(job #3333386)

Utilizator StefiliciHrisca Stefan Stefilici Data 13 ianuarie 2026 10:53:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>
using namespace std;

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

const int MAXN=2000010;

string model,text;
int prefix[MAXN],aparitii[MAXN];
int lgModel,lgText,nrAparitii;

void construiestePrefix(){
    int poz=1,lungime=0;
    while(poz<lgModel){
        if(model[poz]==model[lungime]){
            prefix[poz++]=++lungime;
        }else{
            if(lungime)lungime=prefix[lungime-1];
            else prefix[poz++]=0;
        }
    }
}

void cautaModel(){
    int i=0,j=0;
    while(i<lgText){
        if(text[i]==model[j]){
            i++;j++;
            if(j==lgModel){
                aparitii[++nrAparitii]=i-j;
                j=prefix[j-1];
            }
        }else{
            if(j)j=prefix[j-1];
            else i++;
        }
    }

    fout<<nrAparitii<<"\n";
    if(nrAparitii>1000)nrAparitii=1000;
    for(int i=1;i<=nrAparitii;i++)
        fout<<aparitii[i]<<" ";
}

int main(){
    fin>>model;
    fin>>text;
    lgModel=model.size();
    lgText=text.size();
    construiestePrefix();
    cautaModel();
    return 0;
}