Cod sursa(job #3311069)

Utilizator Lex._.Lex Guiman Lex._. Data 19 septembrie 2025 10:31:39
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <bits/stdc++.h>
#define NMAX 2000001
#define POZ_MAX 1000
using namespace std;

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

int pi[NMAX]; ///pi[i] = lungimea maxima a unui prefix al sirului format din primele i caractere ale lui a care este si sufix
int pozitii[POZ_MAX]; ///pozitiile in care sirul a se potriveste peste sirul b

int main()
{
    string a, b;
    in >> a >> b;
    int n=a.size(), m=b.size();
    int l_prefix=0; ///lungimea unui prefix
    pi[0]=l_prefix;
    for(int i=1; i<n; i++)
    {
        while(l_prefix>0 && a[l_prefix]!=a[i]) ///cat timp nu am gasit o potrivire
        {
            l_prefix=pi[l_prefix-1];
        }
        if(a[l_prefix]==a[i]) ///daca am gasit o potrivire
        {
            l_prefix++;
        }
        pi[i]=l_prefix;
    }
    l_prefix=0;
    int nr_aparitii=0; ///numarul de aparitii ale lui a in b
    for(int j=0; j<m; j++)
    {
        while(l_prefix>0 && a[l_prefix]!=b[j]) ///cat timp nu am gasit o potrivire
        {
            l_prefix=pi[l_prefix-1];
        }
        if(a[l_prefix]==b[j]) ///daca caracterele se potrivesc
        {
            l_prefix++;
            if(l_prefix==n) ///daca am ajuns la finalul sirului a
            {
                if(nr_aparitii<POZ_MAX)
                    pozitii[nr_aparitii]=j-n+1; ///adaugam pozitia de inceput a sirului la vectorul de pozitii

                nr_aparitii++; ///marim numarul de aparitii
            }
        }
    }
    out << nr_aparitii << "\n";
    for(int poz=0; poz<nr_aparitii && poz<POZ_MAX; poz++) ///afisam pozitiile
    {
        out << pozitii[poz] << " ";
    }

    return 0;
}