Tìm sự xuất hiện đầu tiên của một chuỗi từ một vector <string>

Question

Tôi có một vector<string> vectorStrings với các giá trị: ta, bc, ac, st, cer, cda. Tôi muốn tìm sự xuất hiện đầu tiên của bất kỳ chuỗi nào trong vectơ trong chuỗi đầu vào.

ví dụ:

InputStr = "this certainly helps"; 

Trong số chuỗi được đưa ra trong vector, tôi sẽ muốn có một cách để nói "cer" là sự xuất hiện đầu tiên ở vị trí 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 

thực hiện này làm việc, nhưng tôi muốn biết nếu có tồn tại một cách thanh lịch hơn để làm điều này với các thư viện tăng hoặc thư viện std.

Tôi đang làm việc trên Windows và sử dụng Visual Studio 2010.

Answer 1

Đây là sự cố MapReduce.

Trước tiên, bạn muốn chuyển từ vector<string> sang vector<int>, vị trí của chúng, là bản đồ và sau đó bạn muốn giảm giá trị xuống một giá trị theo mức tối thiểu, đó là mức giảm. Đầu tiên, bản đồ. Đây là 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); 
    } 
); 

Bây giờ chúng tôi chỉ đơn giản sử dụng std::min_element để lấy phần tử nhỏ nhất, giảm.

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

Để tìm chuỗi đã được tìm thấy ở đó, đó là một chút đơn giản của iterator số học:

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

Answer 2

Tôi không biết thuật toán tăng chung cho tác vụ này. Thuật toán của bạn là chính xác và nên hoạt động tốt trên các kích thước nhỏ. Nếu bạn có vectơ lớn các chuỗi, bạn có thể muốn sử dụng các cấu trúc cây phức tạp hơn một chút cho nhiệm vụ này. Ví dụ: bạn có thể sắp xếp vectơ chuỗi thành cây để tăng tốc độ tìm kiếm. Bạn cũng có thể sử dụng cây hậu tố.

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