Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: sablon  (Citit de 7168 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
popoiu.george
Vorbaret
****

Karma: 19
Deconectat Deconectat

Mesaje: 162



Vezi Profilul
« : Mai 23, 2010, 17:05:57 »

http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=242

Incerc de ceva timp sa imi dau seama cum sa folosesc KMP pentru problema asta. La indicatiile de rezolvare se spune numai "Se foloseste algoritmul KMP".

Imi puteti da o idee ? Pare o problema importanta si nu vreau sa o "las in aer". In plus, am mai intalnit probleme asemanatoare in 2D.

Multumesc anticipat !
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #1 : Mai 23, 2010, 18:05:58 »

Problema este foarte grea. A fost data prima oara la Olimpiada poloneza din 2004. Poti gasi o rezolvare cu suffix array in articolul de pe site (problema Template). Eu nu mai tin minte cum se face in O(N), poate te ajuta cei care au facut-o in concurs la campion. Thumb up
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
mihai_florea
Strain


Karma: 17
Deconectat Deconectat

Mesaje: 24



Vezi Profilul
« Răspunde #2 : Mai 23, 2010, 22:30:49 »

Pentru O(N) calculezi mai intai functia prefix (din KMP), sa zicem pi.
Fie T[ i] lungimea minima a unui sablon ce poate genera prefixul de lungime i al sirului dat.
Observatia importanta este ca T[ i] este fie i, fie T[ pi [ i]].
Ramane sa te gandesti cand T[ i] este T[ pi [ i] ] ...
Memorat
popoiu.george
Vorbaret
****

Karma: 19
Deconectat Deconectat

Mesaje: 162



Vezi Profilul
« Răspunde #3 : Mai 28, 2010, 20:52:49 »

Nu am reusit sa-mi dau seama de recurenta. O stie cineva ?  Confused
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

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