वेक्टर <string>

Question

से स्ट्रिंग की पहली घटना पाएं मेरे पास vector<string> vectorStrings मान हैं: ta, bc, ac, st, cer, cda। मैं एक इनपुट स्ट्रिंग में वेक्टर में किसी भी तार की पहली घटना को खोजना चाहता हूं।

उदा।

InputStr = "this certainly helps"; 

वेक्टर में दिए गए तार की

, मैं चाहेगा "cer" कहने का एक तरीका स्थिति 5 में पहली घटना थी।

---

int min = 9999999; 
string first; 

for(int i = 0; i < vectorStrings.size(); i++) 
{ 
    int pos = InputStr.find(vectorStrings[i]); 

    if(pos == string::npos) 
     continue; 

    if(pos < min) 
    { 
     min = pos; 
     first = vectorStrings[i]; 
    } 
} 

// values of min and first gives which string occurred first 
// and at the position of it in the input string 

इस कार्यान्वयन काम करता है, लेकिन मुझे पता है कि अगर वहाँ बढ़ावा पुस्तकालयों या एसटीडी पुस्तकालय के साथ यह करने के लिए एक और अधिक सुरुचिपूर्ण तरीका मौजूद है चाहेंगे।

मैं विंडोज पर काम कर रहा हूँ और विजुअल स्टूडियो 2010

Answer 1

यह एक MapReduce समस्या है।

सबसे पहले, आप vector<string> से vector<int> से अपने पदों के लिए जाना चाहते हैं, जो एक मानचित्र है, और फिर आप मान को कम से कम एक मूल्य में कम करना चाहते हैं, जो एक कमी है। सबसे पहले, नक्शा। यह std::transform है।

std::vector<std::string> stuff; 
std::string input; 
// fill stuff and input 
std::vector<int> positions; 
std::transform(
    stuff.begin(), 
    stuff.end(), 
    std::back_inserter(positions), 
    [&](std::string& stuff) { 
     return input.find(stuff); 
    } 
); 

अब हम बस std::min_element का उपयोग सबसे छोटा तत्व प्राप्त करने के लिए, कम।

auto iterator = std::min_element(positions.begin(), positions.end()); 
int index = *iterator; 

स्ट्रिंग है कि वहाँ मिला था खोजने के लिए, यह इटरेटर गणित का एक सरल सा है:

string found = stuff[iterator - positions.begin()]; 

Answer 2

का उपयोग कर रहा इस कार्य के लिए सामान्य बढ़ावा एल्गोरिदम पता नहीं है। आपका एल्गोरिदम सही है और छोटे आयामों पर ठीक काम करना चाहिए। यदि आपके पास स्ट्रिंग के बड़े वेक्टर हैं तो आप इस कार्य के लिए थोड़ा और जटिल पेड़ संरचनाओं का उपयोग करना चाहेंगे। उदाहरण के लिए, आप खोज को तेज करने के लिए पेड़ में अपने वेक्टर के तारों को व्यवस्थित कर सकते हैं। आप प्रत्यय पेड़ का भी उपयोग कर सकते हैं।

Answer 3

class Find 
{ 
public: 
    std::vector<std::string> vectorStrings; 
    std::map<size_t, std::string> positions; 

    size_t find(std::string str) 
    { 
     for(std::vector<std::string>::iterator i = vectorStrings.begin(); 
      i != vectorStrings.end(); 
      ++i) 
     { 
      positions[str.find(*i)] = *i; 
     } 

     return (*(positions.begin())).first; 
    } 
};