c++ - 哪种数据结构和算法适用于此？

Question

我有 1000 根绳子。给定一个需要在所有字符串中搜索的模式，并返回所有包含该模式的字符串。

目前我正在使用 vector 来存储原始字符串。搜索模式，如果匹配，则将其添加到新 vector 中，最后返回 vector 。

int main() {
    vector <string> v;
    v.push_back ("maggi");
    v.push_back ("Active Baby Pants Large 9-14 Kg ");
    v.push_back ("Premium Kachi Ghani Pure Mustard Oil ");
    v.push_back ("maggi soup");
    v.push_back ("maggi sauce");
    v.push_back ("Superlite Advanced Jar");
    v.push_back ("Superlite Advanced");
    v.push_back ("Goldlite Advanced"); 
    v.push_back ("Active Losorb Oil Jar"); 

    vector <string> result;

    string str = "Advanced";

    for (unsigned i=0; i<v.size(); ++i)
    {
        size_t found = v[i].find(str);
        if (found!=string::npos)
            result.push_back(v[i]);
    }

    for (unsigned j=0; j<result.size(); ++j)
    {
        cout << result[j] << endl;
    }
    // your code goes here
    return 0;

}

是否有任何最佳方法可以以更低的复杂性和更高的性能实现相同的目标？？

Answer 1

我认为适合您应用的容器。

但是，如果您实现自己的 KMP 算法，而不是 std::string::find，那么您可以保证时间复杂度是线性的字符串长度 + 搜索字符串。
http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

因此 std::string::find 的复杂度是未指定的。
http://www.cplusplus.com/reference/string/string/find/

编辑:正如此链接所指出的，如果您的字符串长度不大(超过 1000)，那么可能使用 std::string::find 就足够了，因为这里不需要制表等。
C++ string::find complexity