Cod sursa(job #2910772)

Utilizator AxicaVirtosu Alexandra Mihaela Axica Data 24 iunie 2022 23:20:31
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda 3_iulie Marime 1.91 kb
#include <fstream>
#include <cstring>
#define NMAX 2000000
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char A[NMAX+2], B[NMAX+2];
int sol[NMAX+2], nr, a, b, L;
int P[NMAX+2];

int main()
{
    fin>>A+1>>B+1;
    a=strlen(A+1);
    b=strlen(B+1);

   ///calcularea lui P
   P[1]=0;///p[i]=lungimea celei mai lungi secvente terminate pe poz i care este si sufix
   L=0;///lungimea secvenetei dupa regula de mai sus terminata pe poz i-1 cand sunt la poz i
   for(int i=2; i<=a; i++)
   {
       ///mereu compar pe A[i] cu A[L+1] pana gasesc potrivire, altfel actualizez L-ul
       while(L!=0 && A[i]!=A[L+1])
            L=P[L];
       ///iese fie cand L=0, sau cand A[i]=A[L+1], sau ambele
       ///mai fac o verificare
       if(A[i]==A[L+1])
            L++;
       P[i]=L;
   }

   ///timpul este  O(2*a) pt ca L se mareste de maxim a ori(se mareste cu 1 la fiecare pas din for)
   ///iar while-ul din for scade din L nostru, deci nu poate face mai mult de a pasi
   ///in tot for+while =a+a, deci O(a)

   ///utilizarea lui P pentru a rezolva cerinta
   ///L=cea mai lunga secventa din B terminata pe poz i care sa fie prefix a lui A
   ///cand L=a at stim ca am gasit sirul A in sirul B

   L=0;
   for(int i=1; i<=b; i++)
   {
       while(L!=0 && B[i]!=A[L+1])
        L=P[L];
       if(B[i]==A[L+1])
        L++;
       if(L==a)
       {
           nr++;
           if(nr<=1000)
            sol[nr]=i-a;///in prob sirul ni se cere indexat de la 0, noi am lucrat cu el indexat de la 1
           L=P[L];///daca si urm poz va face potrivire nu mai am cu sa cresc L daca e deja a, asa ca fac un pas inapoi
       }
   }
    ///timpul de executie este (2*b) pe ac principiu ca mai sus, adica O(b)

    ///de unde rezulta complexitatea de O(a+b)
    fout<<nr<<"\n";
    for(int i=1; i<=min(nr, 1000); i++)
        fout<<sol[i]<<" ";


    return 0;

}