Cod sursa(job #3306636)

Utilizator gugalcromMuntoiu Vlad-Ioan gugalcrom Data 12 august 2025 16:41:55
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int main() {
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    string model, original;
    fin >> model >> original;
    string sir = model + "$" + original;

    int l = 0, r = 0;
    vector<int> Z(sir.size());
    Z[0] = model.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=model.size()+1; i<sir.size(); ++i) {
        potriviri += Z[i] == model.size();
    }
    fout << potriviri << '\n';
    for(int i=model.size()+1; i<sir.size(); ++i) {
        if(Z[i] == model.size()) {
            fout << i - model.size() - 1 << ' ';
        }
    }
    fout << '\n';

    return 0;
}