शब्दों में स्प्लिट स्ट्रिंग

Question

मैं स्ट्रिंग से शब्दों के सभी संभावित संयोजन बनाने के लिए सबसे कुशल एल्गोरिदम खोज रहा हूं। उदाहरण के लिए:

Input String: forevercarrot 

Output: 

forever carrot 
forever car rot 
for ever carrot 
for ever car rot 

(सभी शब्द एक शब्दकोश से होना चाहिए)।

मैं एक जानवर बल दृष्टिकोण के बारे में सोच सकते हैं। (सभी संभावित सबस्ट्रिंग्स और मैच ढूंढें) लेकिन बेहतर तरीके क्या होंगे?

Answer 1

एक psuedocode कार्यान्वयन, तथ्य यह है कि स्ट्रिंग के हर हिस्से में एक शब्द भी होने की जरूरत है शोषण, हम कुछ भी नहीं जा सकते हैं। हम स्ट्रिंग की शुरुआत से आगे काम करते हैं जब तक कि पहला बिट एक शब्द न हो, और फिर शेष स्ट्रिंग के सभी संभावित संयोजन उत्पन्न करें। एक बार ऐसा करने के बाद, हम तब तक चलते रहते हैं जब तक कि हमें पहले शब्द के लिए कोई अन्य संभावनाएं न मिलें, और इसी तरह। ["for", "ever", allPossibleWords["carrot"]] में ["forever", allPossibleWords["carrot"]] में एक बार और एक बार - अपने उदाहरण में, आप दो बार allPossibleWords("carrot") गणना करने के लिए हो रही अंत होगा -

allPossibleWords(string s, int startPosition) { 
    list ret 
    for i in startPosition..s'length 
     if isWord(s[startPosition, i]) 
      ret += s[startPostion, i] * allPossibleWords(s, i) 
    return ret  
} 

इस कोड में डरावना है कि आप गणना दोहरा खत्म करेंगे। तो यह याद रखना कुछ विचार करना है।

Answer 2

में जाना जाता है शब्द की अपनी सूची के लिए एक prefix tree का प्रयोग करें। शायद myspell जैसी libs पहले से ही ऐसा करते हैं। तैयार किए गए एक का उपयोग करने का प्रयास करें।

एक बार जब आप एक मैच (जैसे 'कार') में पाया गया, अपने गणना विभाजित: एक शाखा शुरू होता है एक नया शब्द ('सड़ांध') देखने के लिए, एक और वर्तमान शुरुआत ('गाजर') के वेरिएंट का पता लगाने के लिए जारी है।

प्रभावी रूप से आप गणना करते समय हर बार अपनी स्ट्रिंग में ऑफसेट्स के (start_position, current_position) जोड़े की कतार बनाए रखते हैं। कई धागे समानांतर में इस कतार से पॉप हो सकते हैं और start_position से शुरू होने वाले शब्द को जारी रखने का प्रयास कर सकते हैं और जोड़ी के पहले से ही current_position तक ज्ञात है, लेकिन वहां समाप्त नहीं होता है। जब कोई शब्द मिलता है, तो इसकी सूचना दी जाती है और एक और जोड़ी कतार से पॉप हो जाती है। जब यह असंभव है, कोई परिणाम उत्पन्न नहीं होता है। जब एक विभाजन होता है, तो कतार के अंत में एक नई जोड़ी जोड़ दी जाती है। प्रारंभ में कतार में (0,0) होता है।

Answer 3

इस प्रश्न को देखें जो बेहतर उत्तर भी है। यह एक मानक गतिशील प्रोग्रामिंग समस्या है:

How to split a string into words. Ex: "stringintowords" -> "String Into Words"?

Answer 4

इनपुट स्ट्रिंग: forevercarrot

आउटपुट:

हमेशा के लिए कभी कार सड़ांध के लिए कभी गाजर के लिए गाजर हमेशा के लिए कार सड़ांध

कार्यक्रम :

#include<iostream> 
#include<string> 
#include<vector> 
#include<string.h> 
void strsplit(std::string str) 
{ 
    int len=0,i,x,y,j,k; 
    len = str.size(); 
    std::string s1,s2,s3,s4,s5,s6,s7; 
    char *c = new char[len+1](); 
    char *b = new char[len+1](); 
    char *d = new char[len+1](); 
    for(i =0 ;i< len-1;i++) 
    { 
     std::cout<<"\n"; 
     for(j=0;j<=i;j++) 
     { 
      c[j] = str[j]; 
      b[j] = str[j]; 
      s3 += c[j]; 
      y = j+1; 
     } 
     for(int h=i+1;h<len;h++){ 
      s5 += str[h]; 
     } 
     s6 = s3+" "+s5; 
     std::cout<<" "<<s6<<"\n"; 
     s5 = ""; 
     for(k = y;k<len-1;k++) 
     { 
      d[k] = str[k]; 
      s1 += d[k]; 
      s1 += " "; 
      for(int l = k+1;l<len;l++){ 
      b[l] = str[l]; 
      s2 += b[l]; 
     } 
     s4 = s3+" "+s1+s2; 
     s7 = s4; 
     std::cout<<" "<<s4<<"\n"; 
     s3 = "";s4 = ""; 
     } 
     s1 = "";s3 = ""; 
    } 
} 

int main(int argc, char* argv[]) 
{ 
    std::string str; 
    if(argc < 2) 
       std::cout<<"Usage: "<<argv[0]<<" <InputString> "<<"\n"; 
    else{ 
       str = argv[1]; 
       strsplit(str); 
    } 

return 0; 
}