554 Superstring

[•DITzoneC]

Aici puteţi discuta despre problema Superstring.

[•fireatmyself]

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

[•DITzoneC]

Da

[•Florian]

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.  Un hint... ceva?

[•wefgef]

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

[•astronomy]

Sau tot O(N+M) folosind hash-uri 

[•wefgef]

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 .

[•CezarMocan]

Imi dati si mie ceva idei cei care ati facut cu hash va rog... ca nu iese nicicum... 

[•astronomy]

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 

[•CezarMocan]

Pai asa fac... adica eu consider in baza 100 (cred   )... 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. 

[•astronomy]

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

[•wefgef]

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.

[•cos_min]

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

[•pauldb]

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

[•cos_min]

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

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.

[•Florian]

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 ? 

[ LE: Ideea e buna. Greseam la implementare. ]

[•cojocarugabi]

am facut o sursa cu complexitate O(n + m),cu parsare si iau tle,ce sa fac sa iau AC.

[•klamathix]

Am mărit limita, ai luat 100 

[•stoianmihail]

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". 
Dintre aceste doua rezultate aleg maximul "max", iar solutia va fi : lungimea lui "a" + lungimea lui "b" - max.

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! 
Multumesc mult!