005 Potrivirea sirurilor

[•Bogdan_tmm]

Zici ca daca vectorul e gol si tu apelezi .size() iti da eroarea aia? Daca e gol .size()=0,nu-ti da eroare

[•Oancea.Catalin]

Poate sa se uite cineva pe sursa mea? Iau doar 14 puncte si am folosit KMP. http://infoarena.ro/job_detail/529187
Multumesc anticipat . 

[•AndrewTheGreat]

Poate sa se uite cineva pe sursa mea? Iau doar 14 puncte si am folosit KMP. http://infoarena.ro/job_detail/529187
Multumesc anticipat . 

f.getline(P,100)? eu aia am sesizat cand ti-am deschis sursa... In rest daca a luat puncte inseamna ca aia e toata greseala  .

[•Oancea.Catalin]

    Mersi... sper sa nu mi se intample asa ceva si la olimpiada 

[•memax]

Asa o intrebare la algoritmul Rabin-Karp din sursa oficiala, de ce hash1 si hash2 se iau modulo cu 2 numere diferite?

[•pauldb]

Pentru ca daca ai folosi acelasi modulo, nu ai miscora deloc probabilitatea unei coliziuni.

Daca intrebi de ce se folosesc uneori doua sau mai multe hash-uri, raspunsul e urmatorul: daca functia ta hash genereaza numere uniform in intervalul [0, M1), atunci ai probabilitate 1/M1 pentru o coliziune. Daca mai adaugi o alta functie hash independenta de prima care returneaza numere uniform in intervalul [0, M2), atunci probabilitatea unei coliziuni scade la 1/M1 * 1/M2. Poti sa vezi tehnica asta ca si cum ai creste intervalul in care returneaza functia hash valorile la [0, M1*M2), dar in acelasi timp eviti calculul pe numere mari.

[•memax]

Multumesc mult, am inteles 

[•taigi100]

Nu inteleg de ce nu vrea sami compileze am incercat si cu File *f=fopen... si cu freopen dar nu mere si imi zice ca nu gaste stdio.h am incercat deasemea cu cstdio si si ala zice ca nu mil gaseste.
http://infoarena.ro/job_detail/795221
http://infoarena.ro/job_detail/795220
http://infoarena.ro/job_detail/795217
vreo idee de ce se intampla asta?

[•Alexxino7]

Dupa ce am experimentat putin cu sursa ta, am observat ca desi pe compilatorul meu codul tau nu da nici o eroare, pe compilatorul infoarena apare ca eroare spatiul lasat in directiva #include<cstdio >. Ca sa nu-ti mai dea eroare pur si simplu nu mai lasi spatiul acela si scrii #include<cstdio>.

[•taigi100]

mda.... ms dar sincer e o eroare un pic cam ridicola

[•taigi100]

Bun... si de asemenea imi puteti da niste exemple pe care sursa mea nu functioneaza? ( nu vreau nici un motiv exact dc. nu functioneaza ci doar niste exemple ca sa ma chinui eu sa o rezolv )
http://infoarena.ro/job_detail/795262

[•Schumi]

Ai acces la atasamentele problemei. Intra la atasamente si descarca-ti testul pe care iti da incorect.

[•taigi100]

nu stiam asta ... multumesc

[•taigi100]

ok dupa vreo 5 ore de incercari tot nu miam prea dat seama ca nu e bun ( e un pic cam greu cu testeke alea tinand cont ca is fooooarte lungi) nu am prea reusit sa fac nimic ... asa ca imi puteti da o mana de ajutor ? algoritmul e un boyer moore

[•Schumi]

Tu afisezi pe prima linie maxim 1000. In problema scrie ca trebuie sa afisezi pe prima linie numarul total de potriviri, iar pe a doua sa le afisezi doar pe primele 1000.

[•taigi100]

Ms, in afara de asta am observat ca la testul 6 imi sare peste un match ceea ce banui ca se intampla de la modul in care cresc i-ul  am incercat sa il fac in mai multe feluri dar nu prea reusesc cum sa obtin peste 38 de pct ( scz ca pun atatea intrebari dar is cam nou  )

[•alex_unix]

Poti sa te uiti peste sursele exemplu care 100% sunt corecte. Si restul surselor sunt libere. Daca tot nu gasesti bug-ul, arunca o privire peste ele. 

[•VisuianMihai]

Am incercat sa rezolv problema prin Z-algorithm si iau 40 de puncte, nu inteleg ce nu e corect.

Later edit: am rezolvat. Nu am vazut ca trebuie afisate primele 1000 pentru testele mari.

[•Opportunity]

salut 22ror
am incercat sa fac problema prin metoda Rabin Karp
am trimis o sursa facuta dupa exemplu oficial
http://infoarena.ro/job_detail/846223?action=view-source
si iau doar 40 puncte
apoi am incercat sa skimb hashul in unul foarte simplu (hash=(ord(a[1])+ord(a[2])...ord(a[n])) mod 100000021
plus am adaugat control manual in caz ca coincide hashul
si tot iau 40 puncte, dar e mai rapid decit cel oficial.. 
http://infoarena.ro/job_detail/846204?action=view-source
help plz.

[•taigi100]

Aveti idee cum pot sa fac mai rapida implementarea la asta :
http://infoarena.ro/job_detail/856786
Fara sa folosesc un good sufix table ( vreau sa raman doar la un BMH nu la un BM)

[•Fayed]

Eu iau 60 de puncte pe problema cu TLE la 2 teste si fac direct cu strstr care este KMP deja optimizat din cate stiu eu. Care ar putea fi problema ? E mai rapid cu hashing ?

[•wefgef]

Functia strstr() are complexitatea O(N^2), nu este KMP.

[•SebiSebi]

Oricum, este foarte surprinzator ca a luat 60 de puncte cu strstr(). 

[•Fayed]

Bine ca mi-ati spus ca e O(n^2). Acum stiu ca trebuie sa invat KMP.

[•Fayed]

Am facut KMP si am luat 100, insa vreau sa fac si Rabin Karp. Am inteles foarte bine cum se face teoretic insa ceva nu imi iese la implementare. Aveti vreo idee ?

Cod:

#include <cstdio>
#include <cstring>
#define NMAX 2000001
#define min(a,b) a<b ? a:b
using namespace std;

char A[NMAX],B[NMAX];
int n,m,nr,a,b;
int Sol[NMAX];
int t[NMAX];

inline unsigned long putere(int x,int k,int MOD){

    if (k == 0)
        return 1;
   else if(k%2 == 0){
       a = putere(x,k/2,MOD);
        return a*a%MOD;
   }
   else{
        a = putere(x,k/2,MOD);
        b = a*a%MOD;
        return b*x % MOD;
   }
}

inline int match(char *T, char *P,int j){

    for(register int i=0;i<m;++i)
        if(T[i+j] != P[i])
            return 0;
return 1;
}

inline void Rabin_Karp(char *T,char *M,int d,int MOD){

    unsigned long h,P=0;
    n = strlen(T);
    m = strlen(M);

        t[0] =0;
        h = putere(d,m-1,MOD);
    for(register int i=0;i<m;++i){
        P = (d*P + M[i])% MOD;
        t[0] = (d*t[0] + T[i])%MOD;
}

    printf("%d\n",P);
    for(register int i=0;i<=n-m;++i){

        printf("%d\n",t[i]);
        if(P == t[i]){
            if(match(T,M,i))
                    Sol[++nr] = i;
                    printf("%d\n",i);
                  }

         t[i+1] = (d*(t[i] - T[i+1]*h) + T[i+m+1])%MOD;
        }
}

int main(){


freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);

fgets(B,sizeof(B),stdin);
fgets(A,sizeof(A),stdin);

    Rabin_Karp(A,B,256,100003);
    printf("%d\n",nr);
    for(register int i=1;i<=min(nr,1000);++i)
        printf("%d ",Sol[i]);

return 0;
}

Editat de admin: Foloseste tagul "code" atunci cand postezi surse.