进行字符串前缀测试的优雅方式

Question

据我所知，标准库中没有直接执行此操作的工具。所以，我想知道一种简单而优雅的方法来做到这一点。请注意，我无意自己编写 is_prefix() 函数。只需使用标准库中已有的内容即可。假设任务是测试 a 是否是 b 的前缀（两者都是 std::string 类型）。

最简洁的方式似乎是b.find(a) == 0。但这需要 O(a.size() * b.size()) 时间。不好。

另外，我们可以做到b.substr(0, a.size()) == a。这需要线性时间。但是它创建了一个新的字符串对象，这可能涉及堆上的动态内存分配。所以，不好。

我们可以写b.size() >= a.size() && std::equal(b.begin(), b.begin() + a.size(), a.begin())。这在运行时性能方面是最优的，但是代码很长。

有什么建议吗？

对于那些想知道我为什么要问这个的人，我想找到一个方便的解决方案以用于 TopCoder SRM 和工作面试。

Answer 1

可以使用std::mismatch算法：

bool is_prefix(const std::string& data, const std::string& prefix)
{
    auto mismatch = std::mismatch(data.begin(),   data.end(),
                                  prefix.begin(), prefix.end()).second;
    return mismatch == prefix.end();
}

Answer 2

对于那些坚持使用旧 Visual Studio 版本的人：

由于 str 必须至少与 prefix 一样长，我们可以使用 3 参数版本，不再需要更新的 c++ 标准。

std::mismatch(prefix.begin(), prefix.end(), str.begin()).first == prefix.end();

进行字符串前缀测试的优雅方式

Elegant way to do a string prefix test

c++

string

c++-standard-library

c++14