Come calcolare i prefissi unici più brevi di un set di stringhe?

Question

È un algoritmo piuttosto comune nella riga di comando che analizza. Dato un insieme di nomi di opzioni lunghi predefiniti - calcola il prefisso più breve che identifica in modo univoco una di queste opzioni. Così, per esempio, per le seguenti opzioni:

-help 
-hostname 
-portnumber 
-name 
-polymorphic 

Questo sarebbe l'output:

-he 
-ho 
-por 
-n 
-pol 

sto pensando due possibili modi per farlo - sia come un albero:

   * 
      /| \ 
      /| \ 
      H N P 
     /\  | 
     E O  O 
       /\ 
       R L 

O la ricerca di stringhe:

for (String s : strings) { 
    for (int i = 1; i < s.length(); s++) { 
     if (search(strings,s.substring(0,i)) == 1) { 
      result.add(s.substring(0,i); 
      break; 
     } 
    } 
} 

Quindi, la domanda è:

1. Quale sceglieresti?
2. Mi manca un'ovvia terza via?

Answer 1

La soluzione "albero" è un caso particolare (beh, in realtà è abbastanza generale) di un Patricia trie.

Il primo sarà generalmente più veloce da cercare. Le considerazioni sulla memoria probabilmente non sono rilevanti per il tuo contesto, dal momento che non vengono utilizzate in modo permanente e stai eseguendo la "ricerca" una sola volta.

Answer 2

Farei l'albero, sembra buono.

È possibile creare un hash di ogni sottostringa distinta possibile.

Hashmap<String, String> validSubs = new Hashmap<String, String>(); 
HashSet<String> usedSubs = new HashSet<String>(); 

for (String option : options) { 
    for(int i = 0; i <= option.length; i++) { 
    String sub = option.substring(0, i); 
    if(usedSubs.contains(sub)) { 
     validSubs.remove(sub); 
    } else { 
     validSubs.add(sub, option); 
     usedSubs.add(sub); 
    } 
    } 
} 

Answer 3

Oh, sì, la risposta mancante più ovvia è usare una libreria che già lo fa. How to parse command line arguments in Java?