Drzavno, 2018, 7-8. razred
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.
Izguglaj KMP algoritam, bice ti jasnije. Takodje moze da se resi i hesovanjem samo sto je to resenje malo sporije.
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])
Hashovanje nije sporije( O(n))?
Da ali imas mnogo operacija modulovanja (valjda se tako kaze) koje su spore
Verovatno prolazi ali ako oces optimalnije onda je to kmp
Zadatak takođe može da se reši u O(n) sa suffix tree.
Ima raznih tehnika, mada na takmicenju je I hashovanje prolazilo.
Suffix tree za osnovne skole najs
To je tek za SIO u osnovnim.
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”)