# Problema OIS remix

**URL:** <https://forum.olinfo.it/t/problema-ois-remix/393>\
**Category:** Aiuto\
**Created:** [30 Novembre 2015, 8:48pm UTC](https://forum.olinfo.it/t/problema-ois-remix/393 "2015-11-30T20:48:59Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![kmfrick](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/k/ba9def/32.png) [@kmfrick](https://forum.olinfo.it/u/kmfrick)\
**Post date:** [30 Novembre 2015, 8:48pm UTC](https://forum.olinfo.it/t/problema-ois-remix/393/1 "2015-11-30T20:48:59Z")

</div>

Ciao people! 😃

Non riesco a capire quale sia il modo corretto per risolvere remix. Ho prima provato a cercare “PaH” e “TuNZ” usando `strstr()`, ma prendo 70/100, e ci sta perché `strstr()` è naive come ricerca se non erro.  
Allora ho provato a usare il [KMP algorithm](https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm), ma prende comunque 70/100…e non solo, va in TLE in ancora più casi di `strstr()`!

Io non ci dormo più la notte xD

---

<div class="post-metadata">

**Author:** ![Carlo](https://forum.olinfo.it/user_avatar/forum.olinfo.it/carlo/32/37_2.png) [@Carlo](https://forum.olinfo.it/u/Carlo)\
**Post date:** [1 Dicembre 2015, 3:03pm UTC](https://forum.olinfo.it/t/problema-ois-remix/393/2 "2015-12-01T15:03:17Z")

</div>

KMP? Hai overkillato (e tanto) il problema, KMP non lo chiedono neanche alle nazionali, figurati alle gare a squadre D:  
Comunque si fa tranquillamente in O(N), dove N è la lunghezza del testo, senza nessun tipo di algoritmo particolare o funzione del C++

(anche perché i due pattern sono sempre PaH e TunZ, a meno di maiuscole diverse, e non si “intersecano” ovvero una volta che ne trovi uno puoi continuare la ricerca saltando le 3/4 lettere dopo)

---

<div class="post-metadata">

**Author:** ![kmfrick](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/k/ba9def/32.png) [@kmfrick](https://forum.olinfo.it/u/kmfrick)\
**Post date:** [1 Dicembre 2015, 4:27pm UTC](https://forum.olinfo.it/t/problema-ois-remix/393/3 "2015-12-01T16:27:34Z")

</div>

Risolto! Mi sono accorto che una soluzione da 70/100 che avevo mandato un anno fa iniziava a cercare da remix[0] ogni volta D:  
Grazie per aver fatto cessare le mie pare mentali xD