Cod sursa(job #3300006)

Utilizator Lex._.Lexi Guiman Lex._. Data 12 iunie 2025 10:32:48
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <bits/stdc++.h>
#define NMAX (int)2e6
#define NR_POZ 1000
using namespace std;

int pi[NMAX]; ///pi[i] = lungimea celui mai lung prefix care este si sufix sirului a[0], a[1], ... a[i]

int main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    string a, b;
    cin >> a >> b;
    int n=a.size(), m=b.size();
    int lung_pref=0; ///lungimea unui prefix
    pi[0]=lung_pref;

    for(int i=1; i<n; i++)
    {
        while(lung_pref>0 && a[lung_pref]!=a[i]) ///cat timp nu am gasit o potrivire
        {
            lung_pref=pi[lung_pref-1];
        }
        if(a[i]==a[lung_pref]) ///daca am gasit o potrivire, marim lungimea prefixului maxim, altfel, lungimea prefixului maxim va fi 0
        {
            lung_pref++;
        }
        pi[i]=lung_pref;
    }

    int nr_aparitii=0; ///numarul de aparitii ale sirului a in sirul b
    vector<int> poz; ///pozitiile pe care apare sirul a in sirul b
    lung_pref=0; ///resetam lungimea prefixului
    for(int i=0; i<m; i++)
    {
        while(lung_pref>0 && a[lung_pref]!=b[i]) ///cat timp nu am gasit o potrivire
        {
            lung_pref=pi[lung_pref-1];
        }
        if(b[i]==a[lung_pref]) ///daca am gasit o potrivire
        {
            lung_pref++;
        }
        if(lung_pref==n) ///daca lungimea prefixului este egala cu m, inseamna ca am gasit o aparitie a lui a in b
        {
            nr_aparitii++; ///marim numarul de aparitii
            if(nr_aparitii<NR_POZ)
            {
                poz.push_back(i-n+1); ///salvam pozitia aparitiei
            }
        }
    }
    cout << nr_aparitii << "\n"; ///afisam numarul de aparitii
    for(auto pozitie : poz)
        cout << pozitie << " "; ///afisam pozitiile primelor 1000 de aparitii

    return 0;
}