检查一个字符串是否是另一个字符串的前缀

Question

我有两个字符串需要进行比较：String 和 String:。是否有库函数能够接收这两个字符串并返回true，但当传入String和OtherString时返回false？

准确地说，我想知道一个字符串是否是另一个字符串的前缀。

- fredley

---

使用经典的 string.compare() 怎么样？ - Alok Save

@Donotalo 那就可以了，如果它能为我完成这项工作，那就太好了，这样我就不需要费力地计算 n 了。 - fredley

严格来说，满足您要求的一个函数是 == 运算符。;-) - Frerich Raabe

@FrerichRaabe：不，它并不想检查它们是否相同，而是想检查它们是否共享一个前缀。 - David Rodríguez - dribeas

这不是 (部分) https://dev59.com/K3I-5IYBdhLWcg3wZ3YR 的复制吗？那个回答比迄今为止这里的任何一个都要好。 - Don Hatch

Answer 1

使用std::mismatch。将较短的字符串作为第一个迭代器范围传递，将较长的字符串作为第二个迭代器范围传递。返回值是一对迭代器，第一个迭代器位于第一个范围内，第二个迭代器位于第二个范围内。如果第一个迭代器到达第一个范围的末尾，则可以知道短字符串是较长字符串的前缀。

std::string foo("foo");
std::string foobar("foobar");

auto res = std::mismatch(foo.begin(), foo.end(), foobar.begin());

if (res.first == foo.end())
{
  // foo is a prefix of foobar.
}

- Nim

---

+1，这实际上可以通过将结果与 begin() 比较而不是 end 来扩展到测试共享前缀而不是前缀本身（并且可以通过减去来获取共同前缀的实际长度）。 - David Rodríguez - dribeas

+1，但如果第二个字符串较短，则存在危险性，因为您将遍历超过其末尾。因此需要检查foo.size() <= foobar.size()。 - Benoit

这很不错，但是James Kanze使用std::equal的解决方案更简单。 - Cassie Dee

注意，我认为你对于大小的担忧已在 C++14 中得到解决。请参考 mismatch 的返回值注释。 - user3731622

在迭代器上不需要使用mismatch()，只需使用compare()。 - Johannes Overmann

Answer 2

这既高效又方便：

str.compare(0, pre.size(), pre) == 0

compare 之所以快速是因为它使用快速的 traits::compare 方法，不需要复制任何数据。

在这里，它将比较 std::min(str.size(), pre.size()) 个字符，但如果两个范围内的字符相等，则还会检查 pre 的长度，并且如果 pre 长度比此长度长，则返回非零值。

请参见 cplusplus.com 上的文档。

我编写了一个测试程序，使用此代码比较给定在命令行上的前缀和字符串。

- Neil Mayhew

---

为什么需要 a.size() >= b.size()？compare() 也可以处理这个问题。 - ony

因为 a.compare 在到达 a 的末尾时会停止，不会查看 b 的剩余字符。如果 b 在末尾包含额外的字符，则它不是 a 的前缀。 - Neil Mayhew

@ony 你说得对！大小比较是不必要的。我刚刚在http://www.cplusplus.com/reference/string/string/compare/上查看了文档，发现`compare`只有在比较的两个字符范围长度相同时才会返回`0`。如果`str`比`pre`短，`compare`将返回一个负值（在我的测试中为`-1`）。我会编辑我的答案，但你应该分享一部分荣誉。然而，我能做的最好的就是点赞你的评论。 - Neil Mayhew

如果str比pre短，并且它们在str的结尾处相等。对于AA和B，它们在第一个字符上不同，因此compare将返回非零结果。答案本身的措辞更清晰。 - Neil Mayhew

这是最好的答案！ - jlstr

Answer 3

如果你知道哪个字符串更短，那么这个过程很简单，只需要先使用较短的字符串来调用std::equal函数即可。如果你不知道哪个字符串更短，可以尝试以下方法：

bool
unorderIsPrefix( std::string const& lhs, std::string const& rhs )
{
    return std::equal(
        lhs.begin(),
        lhs.begin() + std::min( lhs.size(), rhs.size() ),
        rhs.begin() );
}

- James Kanze

---

这并不总是能给你正确的答案。它会返回两个字符串中是否有一个是另一个的前缀。 - Rahat Zaman

Answer 4

std::string(X).find(Y) 的结果为零，当且仅当 Y 是 X 的前缀。

- MSalters

---

这可能不是最有效的方法。编译器需要对其进行内联，否则它还必须在非零偏移量处搜索 Y。 - MSalters

这个表达简洁，但可能不太高效（想象一下如果X很长而且Y不是X的前缀）。 - Frerich Raabe

这就是为什么我自己评论了这个问题。一个好的优化器会识别与零进行比较，找到对应于前面“for”循环中使用的索引变量的比较对象，并将“for”循环替换为“if”语句。 - MSalters

来自未来的信息：请使用 std::string_view :) - Rakete1111

Answer 5

在 C++20 版本之后，我们可以使用 starts_with 函数来检查一个字符串是否以给定的前缀开头。

str.starts_with(prefix)

此外，还可以使用ends_with函数来检查后缀。

- RY_ Zheng

Answer 6

使用string::compare，您应该能够编写如下代码：

bool match = (0 == s1.compare(0, std::min(s1.length(), s2.length()), s2, 0, std::min(s1.length(), s2.length())));

或者，如果我们不想使用length()成员函数：

bool isPrefix(string const& s1, string const&s2)
{
    const char*p = s1.c_str();
    const char*q = s2.c_str();
    while (*p&&*q)
        if (*p++!=*q++)
            return false;
    return true;
}

- Vlad

---

如果 string1 非常长，这种方法可能效率低下 - 调用 length() 是 O(n) 的，而且没有必要知道字符串的确切长度。你只需要知道它是否足够长即可。 - Frerich Raabe

".length() is O(n)"？你是否在查看character_traits表格？请注意，我的翻译可能不够完美，但我会尽力确保翻译的准确性和易读性。 - MSalters

@Frerich：我承认，我不知道这个。但是话说回来，在大多数现代编译器上，它可能是O(1)的。或者，您可以从开头开始比较字符，直到其中一个是\0。 - Vlad

在C++11中，length()函数必须在常数时间内完成；而在C++03中，它应该在常数时间内完成。 - Mike Seymour

@FrerichRaabe 的理由是： 1) 字符串需要在常数时间内知道 begin() 和 end()，迭代器是随机的，因此它们可以在常数时间内进行减法运算，差值就是字符串的大小，因此必须在常数时间内 知道 它。2) 除非字符串使用 ropes（在 C++11 中被禁止，在任何 已知 的现行标准库实现中都未被实现），否则内存是连续的，这意味着 知道 begin() 和 end() 和 知道 size() 是等价的，你需要存储其中两个，并且可以在常数时间内计算出另一个。 - David Rodríguez - dribeas

Answer 7

如果你可以合理地忽略任何多字节编码（比如UTF-8），那么你可以使用strncmp来实现此功能：

// Yields true if the string 's' starts with the string 't'.
bool startsWith( const std::string &s, const std::string &t )
{
    return strncmp( s.c_str(), t.c_str(), t.size() ) == 0;
}

如果您坚持使用高级的C++版本，您可以使用std::equal算法（额外的好处是您的函数也适用于其他集合，而不仅仅是字符串）：

// Yields true if the string 's' starts with the string 't'.
template <class T>
bool startsWith( const T &s, const T &t )
{
    return s.size() >= t.size() &&
           std::equal( t.begin(), t.end(), s.begin() );
}

- Frerich Raabe

---

使用您的std :: equal解决方案时，如果s比t短会发生什么？看起来它可能会读取超出s的末尾。 - teambob

@teambob：你说得对；我增加了答案来检查这两个字符串的大小。 - Frerich Raabe

Answer 8

如何简单地说：

只需要这样：

bool prefix(const std::string& a, const std::string& b) {
  if (a.size() > b.size()) {
    return a.substr(0,b.size()) == b;
  }
  else {
    return b.substr(0,a.size()) == a;
  }
}

C++不是C语言，它更加安全、简单和高效。

已经测试过的环境包括：

#include <string>
#include <iostream>

bool prefix(const std::string& a, const std::string& b);

int main() {
  const std::string t1 = "test";
  const std::string t2 = "testing";
  const std::string t3 = "hello";
  const std::string t4 = "hello world";
  std::cout << prefix(t1,t2) << "," << prefix(t2,t1) << std::endl;
  std::cout << prefix(t3,t4) << "," << prefix(t4,t3) << std::endl;
  std::cout << prefix(t1,t4) << "," << prefix(t4,t1) << std::endl;
  std::cout << prefix(t1,t3) << "," << prefix(t3,t1) << std::endl;

}

如果你使用的是C++17，你可以编写一个更好的版本，使用std::string_view代替：

#include <string>
#include <string_view>

bool prefix(const std::string& a, const std::string& b) {
  if (a.size() > b.size()) {
    return std::string_view(a.c_str(),b.size()) == b;
  }
  else {
    return std::string_view(b.c_str(),a.size()) == a;
  }
}

使用g++ 7的-O3优化选项后，这将折叠为单个memcmp调用，相比旧版本而言，这是一个相当大的改进。

- Flexo

---

为什么要使用 std::for_each + lambda 表达式，而不是噪音较少的范围 for 循环？ - R. Martinho Fernandes

@R.MartinhoFernandes - 已删除。我只是添加了这一部分来展示使用更大的列表进行调用。 - Flexo

这个函数将报告一个空字符串包含任何其他字符串作为其前缀。对于前缀函数来说，使它对称没有意义。 - Tali

这个方法很复杂且效率低下。它总是会创建临时字符串对象，可能涉及堆内存分配，并且可能会抛出异常。 - user7860670

如果我现在重新回答，我一定会使用string_view。 - Flexo

对于更新版本，只需将字符串作为std::string_view参数接受即可。函数内部的构造是不必要的。 - Coral Kashri

Answer 9

最简单的方法是使用substr()和compare()成员函数：

string str = "Foobar";
string prefix = "Foo";

if(str.substr(0, prefix.size()).compare(prefix) == 0) cout<<"Found!";

- user2180737

---

substr 操作通常会复制数据，因此这不是最高效的方法。 - Neil Mayhew

如果你要使用 substr()，你可以简单地写成 str.substr(0, prefix.size()) == prefix。 - ony

Answer 10

您可以使用以下内容：

对于 C++14 或更早版本的编程：

bool has_prefix
    (const std::string& str, const std::string& prefix)  {
    return str.find(prefix, 0) == 0;
}

对于C++17

//it's a little faster
auto has_prefix
    (const std::string& str, const std::string_view& prefix) -> decltype(str.find(prefix) == 0) {
    return str.find(prefix, 0) == 0;
}

- xninja

---

如果字符串没有前缀并且str比prefix长，那么这种方法不会比其他方法慢很多吗？因为find()方法会在str中搜索任何prefix的实例，即使它不在偏移量0处。例如，在前缀为“a”的情况下检查“bbbbbbba”需要搜索整个字符串，找到最后一个“a”，然后返回false，因为它不在偏移量零，而不是仅比较第一个字符后返回false。 - TrentP

@TrentP 是的。使用rfind()代替find()可以解决这个问题，正如在此问题的已接受答案中建议的那样：https://dev59.com/K3I-5IYBdhLWcg3wZ3YR - Don Hatch