Ciao a tutti, ho da preparare un progetto per l'università, ll testo del progetto è questo.
Sia S una collezione di stringhe. Ogni stringa in S è associata ad una serie di tag.
Ad esempio la stringa “ruota” è associata ai tag “automobile” e “panoramica”.
Implementare una struttura dati che permetta di gestire l’inserimento di nuove stringhe e la stampa delle stringhe a partire dai tag.
In particolare, le operazioni possibili sono:
- a elem tag1 ... tagN -1: Associa i tag1 ... tagN (N>=1) alla stringa elem (i tag sono separati da uno spazio, il -1 indica la fine della specifica dell’operazione).
- s subtag -1: Stampa il numero di tutte le stringhe distinte associate ai tag riferiti da “subtag” (il -1 indica la fine della specifica dell’operazione).
- La stringa subtag si riferisce a tutti i tag di cui è prefisso. Ad esempio, il subtag aut si riferisce ai tag automobile, auto, autovettura, autista, ecc.
- Se nessun tag è associato al subtag, stampare la stringa speciale
“missing”.
Note:
- Un elemento può apparire più volte in operazioni di add. Esempio:
- a pesca frutta sport -1
- a pesca colore -1
- a pesca frutta sport -1
- a mela frutta -1
- ogni tag può essere associato ad uno o più elementi. Nell’esempio sopra, frutta è associato sia a pesca che a mela.
INPUT
La lettura dovrà avvenire da standard input. Per ogni test, la prima linea contiene il carattere i e un intero n che rappresenta il numero di operazioni da effettuare.
Le restanti n linee contengono le operazioni da effettuare.
OUTPUT
L’output del programma è dato dalle stampe dell’operazione s.
N.B.: L’ultima riga conterrà la stringa “<END>”.
io l'ho fatto cosi
codice:
ackage progettoalgoritmi;
import java.util.HashMap;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Map;
import java.util.StringTokenizer;
/**
*
* @author salvo
*/
public class Struttura {
private final HashMap<String, String> mappa;
private static BufferedReader br;
private final ArrayList<String> listaDaRitornare;
private final HashSet<String> insieme;
public Struttura() {
this.mappa = new HashMap<String, String>();
this.listaDaRitornare = new ArrayList<String>();
this.insieme = new HashSet<String>();
}
public void leggi() {
br = new BufferedReader(new InputStreamReader(System.in));
Integer n =Integer.MIN_VALUE;
boolean esci;
String id;
try {
id = "continua";
// esce dal ciclo solo quando viene letto <END>
while (!id.equals("<END>")) {
String stringRead = br.readLine();
StringTokenizer st = new StringTokenizer(stringRead, " ");
id = st.nextToken()/*.trim()*/;
esci = true;
if (id.equals("i")) {
n = Integer.parseInt(st.nextToken());
}
// Se si tratta di un add entra in questo if
if (id.equals("a") && n > 0) {
String elem = st.nextToken();
String tag = null;
while (esci) {
if (tag != "-1" && tag != null) {
this.mappa.put(tag, elem);
}
tag = st.nextToken()/*.trim()*/;
if (tag.equals("-1")) {
esci = false;
}
}
n--;
} // Se si tratta di una stampa entra in questo if
else if (id.equals("s") && n > 0) {
String subTag = st.nextToken()/*.trim()*/;
insieme.clear();
for (Map.Entry<String, String> entry : mappa.entrySet()) {
String valore = entry.getKey()/*.trim()*/;
if (valore.startsWith(subTag)) {
insieme.add(valore);
}
}
if (insieme.isEmpty()) {
listaDaRitornare.add("missing");
} else {
listaDaRitornare.add(Integer.toString(insieme.size()));
// System.out.println(lista.size());
}
n--;
}
}
br.close();
} catch (IOException ex) {
System.out.println("Impossibile leggere i dati");
}
for (String string : listaDaRitornare) {
System.out.println(string);
}
}
public static void main(String[] args) {
Struttura struttura = new Struttura();
struttura.leggi();
}
}
il progetto da i risultati che mi aspetto, solo che il tester mi da time limit, dove la sua definezione è : "o va in loop o impiega troppo tempo".
Consigli o da segnalare errori?? mi servirebbe farlo il piu possibile efficiente. Grazie a tutti coloro che mi aiuteranno.
Rispondi quotando
Originariamente inviata da salvodj88
