005 Potrivirea sirurilor

[•bogdan2412]

Aici puteti discuta despre problema Potrivirea sirurilor.

[•Viksen]

nush daca e ceva evident si sunt eu neatent, dar nu inteleg de ce iau SIGSEV. am luat cateva teste si acasa imi merg. e ceva cu evaluatorul sau e de la mine? 

[•bogdan2412]

Ai depasit limita de memorie..

[•Viksen]

ms mult bogdan!

[•free2infiltrate]

uitativa va rog si peste aceasta sursa  "job #168935"  si spunetimi cu as putea sa maresc viteza, pt ca eu nu ma incadrez in timp la 2 teste (banuiesc ca problema apare de la citirea datelor din fisier) 

[•wefgef]

Cu seekeoln in loc de eoln iei 80.

Am trimis doar citirea si de abia se incadreaza in 296 de ms, deci e clar ca trebuie sa citesti altfel. Incearca cu blockread.

[•fogab]

Am incercat sa implementez si sa testez cateva variatii cu o solutie cu hashuri.. si anumite lucruri nu mi se par clare 
 - scanf mai repede decat getline?    am mai gasit informatii referitoare le problema, incepand cu versiunile GNU G++ 2.7.x  functiile IO din C++ sunt (mult) mai lente.. (iar testand aceeasi surse in VC++  rezultatele sunt opuse  - getline aprox. 2 ori mai rapida)..  limita e cam stransa.. oricum o solutie naiva nu se-ncadreaza in timp, deci mi se pare timpul de executie "fortata"
 - chiar daca doua valori hash asociati pt doi subsiruri sunt egali, totusi exista o sansa ca ele sa nu fie identice; de aceea, de obicei se implementeaza o testare "caracter-cu-caracter"; dar o astfel de sursa NU se incadreaza in timp...chiar daca verificarea e facuta pe baza a mai multori functii hash, solutia pierde din generalitatea sa, avand o complexitate O(N) "fortata" - si in unele cazuri chiar va fi mai optima decat KMP

[•devilkind]

pai kmp intra in timp fara nici o problema deci limita de timp nu e stransa. e numai buna ptr a impiedica solutiile cu hash

[•bogdan2412]

Probabilistic sansele gasirii unei aparitii proaste sunt destul de mici. De exemplu daca iei 2 module in jurul valorilor de 1 miliard, respectiv 2 miliarde, prime intre ele, valoarea hashului este determinata unic modulo 2 * 10^18. Deci N (2 milioane) valori se distribuie asupra unui interval de 2 * 10^18. => e probabilitate mica sa gasesti aparitii proaste . In situatii reale sunt folositi destui algoritmi de aproximare pentru ca raportul intre erori si timpul de rulare salvat este extrem de mic.

Sursa mea cu rabin karp intra in 0.2 nu credeam ca o sa fie probleme singura problema cu limita de timp e ca nu cred ca exista vreo sursa in pascal care sa ia 100.

[•stocarul]

Am si eu o problema cu sursa:

http://infoarena.ro/job_detail/263927?action=view-source

Imi greseste cateva teste, si nu vad de ce ......

Le: am descoperit pana la urma ce greseam.

[•Ecthor]

Sunt si eu curios cum ar merge cu "blockread". Nu am inteles foarte bine sintaxa.Din cate am vazut eu, lungimea sirului nu trebuie sa fie mai mare de integer pentru a-l folosi.

[•razyelx]

Puteti sa imi explicati si mie cum functioneaza KMP ca citesc aici in cartea lui Cerchez de vreo 4 ore si nu inteleg ce se face cu functia aia prefix, ce isneamna valorile din vectorul respectiv s.a.m.d.

[•Mishu91]

valoare din pi[ i ] reprezinta cel mai lung prefix al sirului care e sufix al sirului S[ 1 ]S[ 2 ]...S[ i ].
De ex pt sirul a  a c b a  t a  a sirul de prefixe va arata asa.
                      0 1 0 0 1 0 1 2

[•pauldb]

Puteti sa imi explicati si mie cum functioneaza KMP ca citesc aici in cartea lui Cerchez de vreo 4 ore si nu inteleg ce se face cu functia aia prefix, ce isneamna valorile din vectorul respectiv s.a.m.d.

Din cartea doamnei Cerchez.

[•razyelx]

ahhh... scuze. Ai dreptate, cu toate ca am stat 3 ore sa inteleg de ce algoritmul KMP din cartea aia nu merge pe o problema realizand in final ca e gresit, fiind nevoit sa implementez solutia de pe infoarena.

[•Haggis]

Daca are cineva timp, va rog sa va uitati si pe sursa asta http://infoarena.ro/job_detail/300572

Imi da incorect pe 7 teste, si ma holbez la ea de vreo ora da tot nu vad care e cauza.

Mersi.

[•cosser]

Razvan (Haggis), fii atent la functia kmppre(). Esti sigur ca o faci corect? variabila j o scazi numai odata.

[•AnDrEwBoY]

Exista posibilitatea ca |A| > |B| ? Testul 49 asa cred ca este

[•pauldb]

Daca nu se specifica nimic la restrictii, trebuie sa iei in considerare si acest caz.

Totusi, daca te-ai fi uitat pe ok-ul testului 49, ai fi vazut ca raspunsul e 1. (Testele sunt publice la arhiva educationala.)

[•cipriancx]

Am o mica problema la sursa Rabin Karp propusa.
La linia 55 si anume:
hash1 = ((hash1 - (B[i - NA] * P1) % MOD1 + MOD1) * P + B[ i]) % MOD1;

nu inteleg rostul acelui +MOD1 pentru ca atunci cand facem modulo MOD1 acel +MOD1 ar trebui sa fie echivalent cu +0.
Am incercat sa inlocuiesc respectiva linie cu:
hash1 = ((hash1 - (B[i - NA] * P1) % MOD1) * P + B[ i]) % MOD1; iar rezultatul a fost ca mi-ai iesit foarte putine teste.
Imi poate explica cineva cu ce influenteaza acel MOD1?

[editat de moderator] atentie la "[ i]" (fara spatiu), care este un tag special

[•blasterz]

Am o mica problema la sursa Rabin Karp propusa.
La linia 55 si anume:
hash1 = ((hash1 - (B[i - NA] * P1) % MOD1 + MOD1) * P + B) % MOD1;

nu inteleg rostul acelui +MOD1 pentru ca atunci cand facem modulo MOD1 acel +MOD1 ar trebui sa fie echivalent cu +0.
Am incercat sa inlocuiesc respectiva linie cu:
hash1 = ((hash1 - (B[i - NA] * P1) % MOD1) * P + B) % MOD1; iar rezultatul a fost ca mi-ai iesit foarte putine teste.
Imi poate explica cineva cu ce influenteaza acel MOD1?

Tu ai scadere... daca restul iti da negativ nu e bine...asa ca adaugi un MOD1 ca sa devina pozitiv

[•wefgef]

Limbajul nu este atat de inteligent incat sa isi dea seama ca 0 <= X < P si X-P sunt congruente modulo P. Cu alte cuvinte, sa presupunem ca lucrezi mod 7. In matematica 6 si -1 sunt congruente modulo P. Aici insa daca ai un numar negativ si aplici modulo, rezultatul nu va fi cel asteptat.

[•Bogdan_tmm]

Daca am de exemplu sirurile :

cse adcse se

si vreau sa vad care din ele este sufix pentru abadcse. Dupa ce formez numarul lui abadcse cu rabin karp, incerc sa scap de cate o litera de la inceput folosind aceeasi schema ca si la potrivire de siruri dar fara sa mai inmultesc cu baza si sa adun alt element.
sir3=(sir3-(c[j]*Pow1)%MOD1+MOD1)%MOD1
Nu e buna solutia sau gresesc eu ceva?

[•gorgovan]

E normal ca atunci cand folosesc vector<int>(si deci ma bazez pe .size() pentru a-mi spune cate pozitii am gasit) si nu gasesc nici un sir sa primesc SIGSECV ?

[•Mishu91]

Nu am înțeles ce faci de primești SIGSEGV.