|
Titlul: sablon Scris de: George Popoiu din 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 ! Titlul: Răspuns: sablon Scris de: Andrei Grigorean din 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 (http://infoarena.ro/siruri-de-sufixe) 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. :thumbup:
Titlul: Răspuns: sablon Scris de: Florea Mihai Alexandru din 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] ] ... Titlul: Răspuns: sablon Scris de: George Popoiu din Mai 28, 2010, 20:52:49 Nu am reusit sa-mi dau seama de recurenta. O stie cineva ? :?
|