Esercizio: regex?

[dionisoft]

Ciao ragazzi!!
Il mio prof ci ha assegnato questo esercizio per casa, e vorrei un suggerimento (non la soluzione, mi basta capire come risolverlo) sulla sua risoluzione.

Avendo una stringa ed un set di caratteri, identificare la più grande sottostringa che contenga tutti i caratteri del set.

Es.: (ABAMCOAHIFRBC, {A,B,C}) -> BAMC

Ho pensato di scomporre la stringa in un array di char e confrontare ogni carattere con il successivo ed eliminare dal set gli eventuali caratteri incontrati, ma non penso sia il modo migliore di risolvere il problema.

Poi ho pensato alle regex...dite che potrebbero essermi d'aiuto per la risoluzione? C'è un modo per prendere tutte le sottostringhe che contengono tutti i caratteri del set?

Spero in un vostro aiuto, ciao!!

[andbin]

Originariamente inviato da dionisoft
Avendo una stringa ed un set di caratteri, identificare la più grande sottostringa che contenga tutti i caratteri del set.

Es.: (ABAMCOAHIFRBC, {A,B,C}) -> BAMC

No alt. Qui bisogna precisare perché mi pare che la descrizione non collimi molto con l'esempio fatto.

Tutti i caratteri del set una volta sola? O ripetibili? E poi sei sicuro del "più grande"? Perché a me pare che BAMC sia la più piccola che contiene A/B/C.

La più grande accettando ripetizioni sarebbe l'intera stringa ABAMCOAHIFRBC.
La più grande non accettando ripetizioni sarebbe COAHIFRB.

... quindi?

[desa]

Credo si intenda "tutti i caratteri del set una e una sola volta", ma in tal caso è evidente che la soluzione BAMC non è corretta.
Con qualche difficoltà potresti anche riuscire a risolvere il problema con le espressioni regolari... ma non mi pare proprio la via migliore.
Basandomi sull'assunto iniziale che ho fatto sul problema, non vedo perchè la tua soluzione - per quanto generica - non debba andare bene

[dionisoft]

Perdonatemi...ho sbagliato...
Effettivamente è la più piccola!!

Le ripetizioni non sono importanti, l'unica cosa importante è che la sottostringa contenga almeno una volta tutti i caratteri contenuti nel set. Quindi anche un risultato come BDHFGAJAAAAJDFHAAAFJHC andrebbe benissimo!

So che il mio ragionamento fila, ma sto cercando di capire se ci sono soluzioni migliori, tutto qui!!

[dionisoft]

Up!
Nessuna risposta significa che il metodo migliore è quello di analizzare la stringa da zero? :master:

[desa]

Il mio voto l'ho già espresso

[andbin]

Originariamente inviato da dionisoft
Nessuna risposta significa che il metodo migliore è quello di analizzare la stringa da zero? :master:

Io direi di sì, analizzare la stringa con un proprio algoritmo.
Con le espressioni regolari non lo vedo fattibile.

[dionisoft]

Grazie mille ragazzi!!
Se la risposta del prof dovesse esser diversa da quella che mi avete consigliato ve lo farò sapere!!
Ciao!!