Salve a tutti, Non riesco a comprendere a pieno cosa richiede il problema “subs”
Il problema dice:
Data una stringa in input, trovare la sua sottostringa massima secondo l’ordine alfabetico
La richiesta è quindi trovare una sottostringa che soddisfi la contiguità dell’alfabeto? Es. ascdfeadfgjaefr la sotto stringa massima sarebbe “adfgj” giusto? nel caso di “bcdbcdaefg” qual’è la sotto stringa massima che va printata tra “bcd”, “bcd” o “efg”? la prima in ordine lessicografico?
La cosa che mi ha un po confuso le idee è che nel test case bonus formato da 100000 caratteri l’output è 44210 e alla posizione 44210 cè questa stringa […]ysnkfwstaexygqj (dove j è il 44210 esimo carattere) per come ho inteso io il problema la soluzione (su questa porzione di stringa) dovrebbe essere “fwst” oppure “aexy”
Ergo credo di non aver capito cosa il problema richiede.
Hai ragione, il testo non è molto chiaro… Qui ho cercato di spiegarlo meglio:
Comunque, negli esempi che hai portato tu, le soluzioni direi che sono queste:
ascdfeadfgjaefr —> “r”
bcdbcdaefg —> “g”
Un altro esempio: bcdbcda —> “dbcda”
Il fatto che la soluzione sia […]ysnkfwstaexygqj invece di “fwst” oppure “aexy” deriva, banalmente, dal fatto che “y” nell’alfabeto viene dopo di “a” e di “f”
A proposito di questo problema, serve una struttura dati/algoritmo particolare?
mark03
Penso che possa esse risolto con strutture diverse, non so dirti quale sia la migliore perchè non ho ancora provato. Ad occhio potresti utilizzare o una TRIE o ancora meglio un SUFFIX TREE Una volta costruito l'albero in tempo O(n) in base alla struttura scelta vedi come trovarti la sottostringa richiesta dal problema. L'unica cosa di cui non sono convinto è quanta memoria usi se fai una cosa del genere Spero di non aver detto fesserie.
