Razjasnjavanje domina?


#1

O kom takmičenju se radi?

Drzavno, 2018, 7-8. razred

Poruka:

Moze li neko da razjasni kako i zasto radi zvanicno resenje zadatka “domine” sa jucerasnjeg drzavnog takmicenja? Link na resenja je https://dms.rs/wp-content/uploads/2018/04/Drzavno2018saResenjima.pdf, a resenja “domina” se nalazi na poslednjoj strani.


#2

Izguglaj KMP algoritam, bice ti jasnije. Takodje moze da se resi i hesovanjem samo sto je to resenje malo sporije.


#3

Lepo objasnjeno u prvom komentaru, prakticno za svaki prefix [0,i] vrednost kmp[i] je najveca duzina prefixa i sufiksa tako da su oni jednaki (prefixa i sufixa datog prefixa [0,i])


#4

Hashovanje nije sporije( O(n))?


#5

Da ali imas mnogo operacija modulovanja (valjda se tako kaze) koje su spore


#6

Verovatno prolazi ali ako oces optimalnije onda je to kmp


#7

Zadatak takođe može da se reši u O(n) sa suffix tree.


#8

Ima raznih tehnika, mada na takmicenju je I hashovanje prolazilo.


#9

Suffix tree za osnovne skole najs


#10

To je tek za SIO u osnovnim.


#11

Prema onom programu takmicenja na takprog-u, KMP, hesovanje i suffix tree ne dolaze ni na SIO za srednje skole(nalaze se u “Znanja koja se ne zahtevaju”)