Cod sursa(job #3299981)

Utilizator rapidu36Victor Manz rapidu36 Data 12 iunie 2025 09:59:56
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

const int N = 1000;

int main()
{
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");
    string a, b;
    in >> a >> b;
    int m = (int)a.length();
    vector <int> pi(m);
    int 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 += 1;
        }
        pi[i] = lung_pref;
    }
    vector <int> poz(N);
    int n = (int)b.length(), 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 += 1;
        }
        if (lung_pref == m)
        {
            nr_potriviri += 1;
            if (nr_poz < N)
            {
                poz[nr_poz++] = i - m + 1;
            }
        }
    }
    out << nr_potriviri << "\n";
    for (int i = 0; i < nr_poz; i++)
    {
        out << poz[i] << " ";
    }
    in.close();
    out.close();
    return 0;
}