Performance for tags for cars in Java
Variables, scope, naming

Since you have only one method (main), there's no need to declare trovato and ok outside of it. Move them inside main, and make them local variables.

On the other hand, the variables a, ii, and s are for constant strings, indicating special commands in your command line interface, so it would be good to make them constants, loud and clear at the top of the class, with meaningful names, for example:

public static final String ADD_COMMAND = "a";
public static final String ITEM_COMMAND = "i";
public static final String SEARCH_COMMAND = "s";


The same goes for the &lt;END&gt; marker, which didn't have its own variable and it deserves to have one:

public static final String END_MARKER = "&lt;END&gt;";


Your program becomes instantly more readable. These constants are now also protected from mistakes: you cannot accidentally reassign their values, as they are final.

Furthermore, the variables trovato, cont and ok are actually only used when you're processing ADD_COMMAND. You should declare and initialize them there. This will also make it clear and easy to see that you don't need to reset their values at the end of the loop.

Good coding practices

Use interface types when declaring variables (and function parameters). Instead of this:


HashMap&lt;String, HashSet&lt;String&gt;&gt; map = new HashMap&lt;String, HashSet&lt;String&gt;&gt;();
// ...
map = new HashMap&lt;String, HashSet&lt;String&gt;&gt;();
// ...
HashSet&lt;String&gt; hs = new HashSet&lt;String&gt;();



Do like this:

Map&lt;String, Set&lt;String&gt;&gt; map = new HashMap&lt;String, Set&lt;String&gt;&gt;();
// ...
map = new HashMap&lt;String, Set&lt;String&gt;&gt;();
// ...
Set&lt;String&gt; hs = new HashSet&lt;String&gt;();


And try to think of better names for your maps and sets instead of map and hs. For example cars and tags.




BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));



Calling this BufferedReader as stdin is confusing and it invites mistakes. stdin is really System.in itself. A better name would be reader, or bufferedReader.



Always use braces with if statements. Instead of:


if (cont == 2) 
    ok = true;



Do like this:

if (cont == 2) {
    ok = true;
}


Simplify

Notice the duplicated line in this code:


stringa += letteraPerLettera[i];
if (map.containsKey(stringa)) {
    map.get(stringa).add(elemento);
} else {
    Set&lt;String&gt; hs = new HashSet&lt;String&gt;();
    map.put(stringa, hs);
    map.get(stringa).add(elemento);
}



You can simplify:

stringa += letteraPerLettera[i];
if (!map.containsKey(stringa)) {
    Set&lt;String&gt; hs = new HashSet&lt;String&gt;();
    map.put(stringa, hs);
}
map.get(stringa).add(elemento);


This is not very efficient though, because you search for stringa twice: first with containsKey and then again with get. This is equivalent and more efficient:

Set&lt;String&gt; hs = map.get(stringa);
if (hs == null) {
    hs = new HashSet&lt;String&gt;();
    map.put(stringa, hs);
}
hs.add(elemento);


Last words...

Even with the above improvements, I find this code almost unreadable. They way you process the lines, it's just far more complicated than it needs to be. For example, instead of processing the ADD_COMMAND letter by letter, it would make more sense, and more readable to process word by word, like this:

String[] parts = line.split(" ");

// 0: the command, 1: the car name, 2, ...: tags, length-1: -1 (???)
for (int i = 2; i &lt; parts.length - 1; ++i) {
    String car = parts[1];
    String tag = parts[i];
    for (int j = 1; j &lt;= parts[i].length(); ++j) {
        String tagPrefix = tag.substring(0, j);
        Set&lt;String&gt; cars = map.get(tagPrefix);
        if (cars == null) {
            cars = new HashSet&lt;String&gt;();
            map.put(tagPrefix, cars);
        }
        cars.add(car);
    }
}


This is almost the same as the original program, except it also fixes a bug: the original program drops the last letter of car names (resulting in "Dun", and "Nissa"), this one doesn't.

On a related note, do you really need the -1 at the end of lines? It would be easy to make it work without them.

Instead of using a BufferedInputReader, a Scanner can be easier to work with. I recommend to take a look at it (hint: Scanner scanner = new Scanner(System.in))