Cod sursa(job #3321464)

Utilizator Luca07Nicolae Luca Luca07 Data 9 noiembrie 2025 16:22:08
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include<fstream>
#include<vector>
#include<string>
using namespace std;

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

vector<int> lps;

void compute_lps(string pat){
    lps.resize(pat.size(),0);
    int n=pat.size(),i=1,len=0;
    while(i<n){
        if(pat[len]==pat[i]){
            len++;
            lps[i]=len;
            i++;
        }
        else{
            if(len!=0){
                len=lps[len-1];
            }
            else{
                i++;
            }
        }
    }
}


int main(){
    int i,j,lenp,lent,nr;
    string pat,text;

    cin>>pat;
    cin>>text;
    
    compute_lps(pat);
    
    vector<int> vres;
    lenp = pat.size();
    lent = text.size();
    i=0;
    j=0;
    while(i<lent){
        if(text[i]==pat[j]){
            j++;
            if(j==lenp){
                vres.push_back(i-lenp+1);
                if(vres.size()==1000){
                    break;
                }
                j=lps[j-1];
            }
            i++;
        }
        else {
            if(j>0){
                j = lps[j-1];
            }
            else{
                i++;
            }
        }
    }

    cout<<vres.size()<<"\n";
    for(auto i:vres){
        cout<<i<<" ";
    }

    return 0;
}