Cod sursa(job #3141552)

Utilizator mariusn01Marius Nicoli mariusn01 Data 14 iulie 2023 15:34:38
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.33 kb
/**
Avem un text B cu lungimea m. m<=100000
Avem si un cuvant A de lungime n. n<=100000
Cuvantul poate fi oricat de lung.

Toate aparitiile cuvantului ca secventa in text.
**/

#include <fstream>
#include <cstring>
using namespace std;
char a[2000002], b[2000002];
int sol[1001], p[2000001];
int n, m, L, k, i;
ifstream fin ("strmatch.in");
ofstream fout("strmatch.out");
int main () {
    fin>>(a+1)>>(b+1);
    n = strlen(a+1); /// ma intereseaza din a caractere pe pozitii de la 1 la n
    m = strlen(b+1); /// ma intereseaza din b caractere pe pozitii de la 1 la m

    /// KMP obtine timp de calcul liniar (n+m)
/**
    Pasul 1.
    Facem o preprocesare pe cuvantul a.
    Vom construi, pentru fiecare pozitie i din a (de la 1 la n)
    o valoare p[i] = lungimea maxima a unui sufix terminat la pozitia i
                     care este totodata si prefix (si sa nu fie chiar identic cu toata secventa)
    numele p vine de la prefix

    sirul a
       i
    abaxababcxyab
    0010123200012
**/
    p[1] = 0;
    L = 0;
    for (i=2;i<=n;i++) {
        /// calculez pe p[i] (ma voi folosi de faptul ca am p calculat pentru pozitiile anterioare)
        /// in cadrul algoritmului, valoarea ultimului p calculat, adica
        /// p[i-1] o tin intr-o variabila L (care va fi updatata si atribuita lui p[i])

        while (L != 0 && a[i] != a[L+1])
            L = p[L];
        /// am tot scurtat sufixele de la pozitia i care sunt si prefixe
        /// pana cand fie am ajuns la 0 fie am gasit ca pe unul dintre ele il
        /// pot extind
        if (a[i] == a[L+1]) /// in particular asta poate fi si cand L=0
            L++;
        p[i] = L;
    }
    /// codul de mai sus este liniar.
    /// while consuma strict din cresterile lui L
    /// dar L este incrementat cu 1 intr-un if din for
    /// deci numarul total de pasi ai lui while nu poate fi mai mai mare ca L-1

    /**
    pe sirul aaaaaaa, p ar fi fost
       p     0123456
    **/

    /**
    Pasul 2
    in situl b (textul) la o anumita pozitie i, vom calcula L ca fiind
    lungimea maxima a unui sufix din b (terminat la pozitia i)
    care este totodata prefix in a.
    Automat, daca gasesc un astfel de sufix in b care este prefix de lungime
    chiar n in a, inseamna ca am o potrivire.
    **/

    L = 0;
    for (i=1;i<=m;i++) {
        while (L!=0 && b[i] != a[L+1])
            L = p[L];
        /**
        L este valoarea calculata la pasul i-1
        cautam ca elemenul curent din b sa extinda acest predix de lungime L
        din a, iar daca nu se poate il scurtam pe acest prefix candidat ca la
        codul anterior
        **/
        if (b[i] == a[L+1])
            L++;

        if (L == n) {
            k++;
            if (k <= 1000)
                sol[k] = i-n+1; /// cu indexare de la 1
            L = p[L];   /// nu mai putem extinde prefixul de lungime n
                        /// ci cel mai bun prefix al sau
        }
    }
    fout<<k<<"\n";
    if (k > 1000)
        k = 1000;
    for (i=1;i<=k;i++)
        fout<<sol[i]-1<<" ";
}



/**
    brut are complexitate
    for (i=1;i<=m-n+1) {
        /// verificam daca sirul a apare ca secventa in b incepand cu pozitia i
        ok = 1;
        for (j=1;j<=n;j++)
            comparam(a[j] cu b[i+j-1]);
    }
    duce la n*m
**/