Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: 554 Superstring  (Citit de 4650 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
DITzoneC
Nu mai tace
*****

Karma: 301
Deconectat Deconectat

Mesaje: 962



Vezi Profilul
« : Octombrie 10, 2007, 00:35:34 »

Aici puteţi discuta despre problema Superstring.
Memorat
fireatmyself
Nu mai tace
*****

Karma: 36
Deconectat Deconectat

Mesaje: 492



Vezi Profilul
« Răspunde #1 : Octombrie 10, 2007, 12:34:59 »

S1 poate fi inclus in S2? (sau vice-versa)
Memorat

Viata e scurta. Daca nu o putem lungi, macar s-o facem lata.
DITzoneC
Nu mai tace
*****

Karma: 301
Deconectat Deconectat

Mesaje: 962



Vezi Profilul
« Răspunde #2 : Octombrie 10, 2007, 22:24:01 »

Da
Memorat
Florian
Nu mai tace
*****

Karma: 125
Deconectat Deconectat

Mesaje: 832



Vezi Profilul
« Răspunde #3 : Octombrie 24, 2007, 16:06:40 »

Cam ce complexitate ar trebui sa aiba algoritmul? Am ceva in genu O ( N*N) + O (M*M) (unde m, n sunt lungimile celor doua siruri), si iau TLE.  Cry Un hint... ceva?
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #4 : Octombrie 24, 2007, 16:19:36 »

O(N+M) folosind algoritmul Knuth-Morris-Pratt pentru potrivirea sirurilor.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
astronomy
Nu mai tace
*****

Karma: 204
Deconectat Deconectat

Mesaje: 492



Vezi Profilul
« Răspunde #5 : Octombrie 24, 2007, 16:22:44 »

Sau tot O(N+M) folosind hash-uri  Very Happy
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #6 : Octombrie 24, 2007, 20:13:39 »

E mai elegant si mai sigur cu KMP. In plus, nu toate problemele la care ai nevoie de KMP sau de functia prefix a unui sir se pot rezolva cu hash-uri, asa ca nu strica sa inveti ceva nou.

La problema asta insa merg hash-urile de minune Tongue.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
CezarMocan
Nu mai tace
*****

Karma: 252
Deconectat Deconectat

Mesaje: 567



Vezi Profilul
« Răspunde #7 : Octombrie 29, 2007, 20:49:54 »

Imi dati si mie ceva idei cei care ati facut cu hash va rog... ca nu iese nicicum...  Fighting
Memorat
astronomy
Nu mai tace
*****

Karma: 204
Deconectat Deconectat

Mesaje: 492



Vezi Profilul
« Răspunde #8 : Octombrie 30, 2007, 11:17:28 »

Trebuie sa faci o functie de hash buna, de exemplu consideri un sir de litere mici un numar in baza 26 si il calculezi modulo un numar prim mare (sau poti calcula modulo 2 numere prime pentru siguranta). Dupa ce iti iese cu hash-uri sa faci si KMP, ambele sunt bine de stiut  Thumb up
Memorat
CezarMocan
Nu mai tace
*****

Karma: 252
Deconectat Deconectat

Mesaje: 567



Vezi Profilul
« Răspunde #9 : Octombrie 30, 2007, 16:15:37 »

Pai asa fac... adica eu consider in baza 100 (cred   Think)... dar daca fac cu % atunci imi iese din timp. Asa ca fac cu & (2^31-1)... si asa intra in timp... dar daca nu fac verificarea iau incorect, si daca verific iau TLE.  d'oh!
Memorat
astronomy
Nu mai tace
*****

Karma: 204
Deconectat Deconectat

Mesaje: 492



Vezi Profilul
« Răspunde #10 : Octombrie 30, 2007, 17:01:35 »

Vezi cu baza 29 daca iti merge, nu cred ca e prea bine sa aiba divizori comuni baza si numarul care faci modulo.
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #11 : Octombrie 30, 2007, 19:37:42 »

Hash-urile astea te pot scoate din incurcatura de multe ori. Eu personal nu stiu mai deloc hash-uri, insa astronomy de exemplu a luat aur la BOI multumita lor.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
cos_min
Nu mai tace
*****

Karma: 48
Deconectat Deconectat

Mesaje: 493


live


Vezi Profilul
« Răspunde #12 : Ianuarie 05, 2008, 23:11:11 »

Trebuie optimizat ceva ? Am aplicat de doua ori functia KMP, dar iau TLE.
Memorat

vid...
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #13 : Ianuarie 06, 2008, 00:09:36 »

Ar trebui sa fie de ajuns. Te poti uita in articol cum poate fi implementat KMP-ul rapid. Smile
Memorat

Am zis Mr. Green
cos_min
Nu mai tace
*****

Karma: 48
Deconectat Deconectat

Mesaje: 493


live


Vezi Profilul
« Răspunde #14 : Ianuarie 06, 2008, 11:22:49 »

Ar trebui sa fie de ajuns. Te poti uita in articol cum poate fi implementat KMP-ul rapid. Smile

Pai cam asa am implementat. Nu imi dau seama ce poate fi.

LE. Mi-am gasit greseala. Era o greseala de implementare a functiei de potrivire.
« Ultima modificare: Ianuarie 06, 2008, 11:36:17 de către Bondane Cosmin » Memorat

vid...
Florian
Nu mai tace
*****

Karma: 125
Deconectat Deconectat

Mesaje: 832



Vezi Profilul
« Răspunde #15 : Aprilie 01, 2009, 21:16:48 »

La problema asta, nu este suficient sa caut sirul mai scurt in cel lung, iar daca nu ii gasesc nicio aparitie ( <=> sirul scurt nu e inclus in cel lung), sa caut cel mai lung prefix al sirului s1, care este sufix pentru s2 ( si invers : cel mai lung prefix a lui s2, care este sufix pt s1), iar apoi sa aleg minimul global ? Desi mi se pare corect, iau WA. Ce cazuri scap ?  Think

[ LE: Ideea e buna. Greseam la implementare. ]
« Ultima modificare: Aprilie 02, 2009, 18:42:58 de către Marcu Florian » Memorat
cojocarugabi
Strain
*

Karma: -17
Deconectat Deconectat

Mesaje: 25



Vezi Profilul
« Răspunde #16 : August 14, 2015, 00:16:08 »

am facut o sursa cu complexitate O(n + m),cu parsare si iau tle,ce sa fac sa iau AC.
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #17 : August 14, 2015, 00:40:23 »

Am mărit limita, ai luat 100  Smile
Memorat
stoianmihail
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 11



Vezi Profilul
« Răspunde #18 : August 30, 2015, 19:53:56 »

Va rog, imi poate spune si mie cineva(care a rezolvat problema pe baza KMP)daca ideea mea este cea buna(am primit WA)?

Am spus ca sirul "a" este sirul cel mai mic din pereche si ca "b" este sirul cel mai mare din pereche.

Intai m-am uitat sa vad daca "a" este prefix al lui "b". Daca este, atunci solutia va fi lungimea lui "b".
Daca nu, calculam cel mai lung prefix al lui "a" care este sufix al lui "b" si cel mai lung prefix al lui "b" care este sufix al lui "a".  wink
Dintre aceste doua rezultate aleg maximul "max", iar solutia va fi : lungimea lui "a" + lungimea lui "b" - max. Very Happy

Pentru a calcula cele doua rezultate am folosit de doua ori functia prefix de la KMP, cu doua mici modificari(am pus "p" in loc de "str"):

Cod:
int preprocessing(char *str, int n, char *p) {
  int i, k = 0;
  for (i = 1; i < n; i++) {
    while ((k > 0) && (str[i] != p[k])) {
      k = pi[k - 1];
    }
    if (str[i] == p[k]) {
      k++;
    }
    pi[i] = k;
  }
  return k;
}

ID : http://www.infoarena.ro/job_detail/1479236

Am vazut ca la comentarii toti vorbesc de KMP, dar eu nu imi dau seama unde sa-l folosesc!  Confused
Multumesc mult!  Very Happy
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines