Cod sursa(job #3235123)

Utilizator PsyDuck1914Feraru Rares-Serban PsyDuck1914 Data 15 iunie 2024 09:39:58
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.92 kb
#include <fstream>
#include <cstring>

using namespace std;

const int N = 2e6;
const int N_AFIS = 1000;

char a[N+2], b[N+2], aux_a[N+1], aux_b[N+1];
int pref[N+1], potriviri[N_AFIS];

int main()
{
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");
    in >> aux_a >> aux_b;
    strcpy(a + 1, aux_a);///citim de la pozitia 1
    strcpy(b + 1, aux_b);
    ///deocamdata prelucram doar sirul a
    ///construim vectorul pref cu semnificatia:
    ///pref[i] = j <=> j este lungimea maxima a unui prefix care e sufix al pref. de lung. i
    ///si j < i (a[1] = a[i-j+1] si a[2] = a[i-j+2] si ... a[j] = a[i])
    int m = strlen(a + 1), lung_p;
    pref[1] = lung_p = 0;///nu exista prefix de lungime < 1
    for (int i = 2; i <= m; i++)
    {
        while (lung_p > 0 && a[i] != a[lung_p+1])///nu putem adauga a[i] la pref. curent
        {
            lung_p = pref[lung_p];
        }
        if (a[i] == a[lung_p+1])
        {
            lung_p++;
        }
        pref[i] = lung_p;
    }
    int n = strlen(b + 1), n_potriviri = 0;
    lung_p = 0;
    for (int j = 1; j <= n; j++)
    {
        ///pe fiecare pozitie b gasim cel mai lung prefix din a care este sufix al
        ///prefixului de lungime j din b
        while (lung_p > 0 && b[j] != a[lung_p+1])
        {
            lung_p = pref[lung_p];
        }
        if (b[j] == a[lung_p+1])
        {
            lung_p++;
        }
        if (lung_p == m)///intregul sir a este sufix al prefixului de lung j al lui b
        {
            n_potriviri++;
            if (n_potriviri < N_AFIS)
            {
                ///se termina pe poz j, deci incepe pe j - m + 1
                potriviri[n_potriviri-1] = j - m + 1;
            }
        }
    }
    out << n_potriviri << "\n";
    n_potriviri = min(n_potriviri, N_AFIS);
    for (int i = 0; i < n_potriviri; i++)
    {
        out << potriviri[i] - 1 << " ";
    }
    out << "\n";
    in.close();
    out.close();
    return 0;
}