Cod sursa(job #3300146)

Utilizator RuxandraPro12_Metehau Ruxandra Maria RuxandraPro12_ Data 13 iunie 2025 12:16:10
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <fstream>
using namespace std;

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

int pi[2000005], poz[2000005];

int main() {
    string a, b;
    fin >> a >> b;
    int m = a.size(), lung_pref = 0;
    pi[0] = lung_pref;
    for (int i = 1; i < m; i++) {
        while (lung_pref > 0 && a[i] != a[lung_pref])
            lung_pref = pi[lung_pref - 1];
        if (a[i] == a[lung_pref])
            lung_pref++;
        pi[i] = lung_pref;
    }
    int n = b.size(), nr_poz = 0, nr_potriviri = 0;
    lung_pref = 0;
    for (int i = 0; i < n; i++) {
        while (lung_pref > 0 && b[i] != a[lung_pref])
            lung_pref = pi[lung_pref - 1];
        if (b[i] == a[lung_pref])
            lung_pref++;
        if (lung_pref == m) {
            nr_potriviri++;
            if (nr_poz < 1000)
                poz[nr_poz++] = i - m + 1;
        }
    }
    fout << nr_potriviri << "\n";
    for (int i = 0; i < nr_poz; i++)
        fout << poz[i] << " ";
    fout << "\n";
    return 0;
}