स्ट्रिंग्स के सेट के सबसे छोटे अद्वितीय उपसर्गों की गणना कैसे करें?

Question

कमांड लाइन पार्सिंग में यह एक बहुत ही आम एल्गोरिदम है। पूर्वनिर्धारित लंबे विकल्प नामों के एक सेट को देखते हुए - सबसे कम उपसर्ग की गणना करें जो विशिष्ट रूप से इन विकल्पों में से किसी एक को पहचानता है।

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

: - तो उदाहरण के लिए, निम्नलिखित विकल्पों के लिए: या तो एक पेड़ के रूप

-he 
-ho 
-por 
-n 
-pol 

मैं ऐसा करने के दो संभव तरीके में सोच रहा हूँ:

-help 
-hostname 
-portnumber 
-name 
-polymorphic 

यह आउटपुट होगा

या सबस्ट्रिंग को खोजते हुए:

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; 
     } 
    } 
} 

तो, सवाल यह है:

1. आप किसके लिए जाएंगे?
2. क्या मुझे एक स्पष्ट तीसरा तरीका याद आ रहा है?

Answer 1

"पेड़" समाधान Patricia trie का एक विशेष मामला है (ठीक है, वास्तव में यह सामान्य सामान्य है)।

पहला आम तौर पर देखने के लिए तेज़ होगा। मेमोरी विचार शायद आपके संदर्भ के लिए प्रासंगिक नहीं हैं, क्योंकि इसका स्थायी रूप से उपयोग नहीं किया जाता है और आप केवल एक बार "लुकअप" कर रहे हैं।

Answer 2

मैं पेड़ करूँगा, ठीक दिखता है।

आप प्रत्येक संभावित विशिष्ट सबस्ट्रिंग का हैश बना सकते हैं।

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

ओह, हाँ, सबसे स्पष्ट लापता उत्तर एक पुस्तकालय का उपयोग करना है जो पहले से ही ऐसा करता है। How to parse command line arguments in Java?