Ehilà, spero di essere l’unico stupido che non aveva capito la richiesta di questo problema, tuttavia aggiungerei un esempio in cui si può notare che l’output non deve essere solo il minimo numero di stringhe distinte per ricomporre il testo ma che bisogna considerare anche le ripetizioni delle suddette.
Ovvero, se uso n volte la stringa aab allora la devo contare n volte.
Per com’è ora (magari sono pure io che sono un impedito a leggere) non è molto chiaro questo aspetto.
in che complessità l’hai risolto?
Dovrebbe essere O(|N|+|S|^2)
io avevo scritto un algoritmo con tempo O(|N|+|S|^2log|S|^2) e spazio O(|N|+|S|^2) ma |S|^2 di spazio in memoria non ci sta.
quanto spazio usi?
Probilmente il fattore log io l’ho scalato con una hashmap, quindi la mia complessità è peggiore al caso pessimo.
Comunque di spazio \Theta(|N|+|S|) 
Se hai avuto la mia stessa idea allora compatta la struttura dati per tenere S
non uso particolari strutture dati, se non i rolling hash
Io ho usato un Trie per tenere tutti i suffissi di S, scrivendolo in modo furbo puoi mantenere un costo lineare in spazio
ho fatto 100/100 usando un suffix tree (suffix trie compresso) che occupa spazio O(|S|) e viene costruito in tempo O(|S|^2). Usando algoritmi come Ukkonen, il suffix tree può essere costruito in tempo lineare, portando tutta la risoluzione del problema a O(|N|+|S|) per tempo e spazio.
Io mi sono fermato alla costruzione in O(|S|^2) perché bastava con le limitazioni