Cod sursa(job #3306660)

Utilizator gugalcromMuntoiu Vlad-Ioan gugalcrom Data 12 august 2025 17:01:58
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int main() {
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    string sir, original;
    fin >> sir >> original;
    int dimModel = sir.size();
    sir.push_back('#');
    sir.append(original);

    int l = 0, r = 0;
    vector<int> Z(sir.size());
    for(int i=1; i<sir.size(); ++i) {
        if(i > r) {
            l = i;
            for(r=i; r < sir.size() && sir[r] == sir[r-i]; ++r);
            --r;
            Z[i] = r - l + 1;
        } else if(Z[i-l] < r-i+1) {
            Z[i] = Z[i-l];
        } else {
            l = i;
            for(r=i; r < sir.size() && sir[r] == sir[r-i]; ++r);
            --r;
            Z[i] = r-l+1;
        }
    }
    
    int potriviri = 0;
    for(int i=dimModel+1; i<sir.size(); ++i) {
        potriviri += Z[i] == dimModel;
    }
    fout << potriviri << '\n';
    int afisate = 0;
    for(int i=dimModel+1; afisate<1000 && i<sir.size(); ++i) {
        if(Z[i] == dimModel) {
            ++afisate;
            fout << i - dimModel - 1 << ' ';
        }
    }
    fout << '\n';

    return 0;
}