C++：在子字符串数组中高效地查找字符串。

14 浏览
0 Comments

C++：在子字符串数组中高效地查找字符串。

我有一个字符串前缀的数组：std::vector haystack = {"/bin/", "/usr/bin/", "/usr/local/bin/"}。

有没有一种高效的方法，使用标准C++库，查找std::string needle = "/bin/echo"是否以haystack中的子字符串开头？

如果我需要找到完全匹配的情况，我可以使用std::set，它会执行高效的二分搜索，但是我只需要匹配字符串的第一部分，所以目前我是使用一个简单的循环来做：

for (auto it = haystack.begin(); it != haystack.end(); it++) {
    if (needle.compare(0, it->size(), *it) == 0) {
        return true; // 找到了
    }
}
return false;

0

2 答案

0 Comments

C++: 高效地在一个子字符串数组中查找一个字符串的问题是如何出现的呢？出现这个问题的原因是只需要在数组中找到第一个匹配项，而不需要找到所有匹配项。为了解决这个问题，可以使用std::any_of函数来进行优化，它在找到第一个子字符串匹配项后会立即停止搜索。

以下是使用std::any_of函数来解决这个问题的代码示例：

auto found = std::any_of(begin(haystack),
                         end(haystack),
                         [&needle](std::string const& sub)
                         { 
                             return needle.compare(0, sub.size(), sub) == 0;
                         });

另外，如果需要找到匹配的子字符串，可以使用std::find_if函数，它也会在找到第一个匹配项后立即停止搜索。

以下是使用std::find_if函数来解决这个问题的代码示例：

auto match = std::find_if(begin(haystack),
                          end(haystack),
                          [&needle](std::string const& sub)
                          { 
                              return needle.compare(0, sub.size(), sub) == 0;
                          });

以上是解决C++: 高效地在一个子字符串数组中查找一个字符串的问题的方法。

0
0 Comments

C++: 高效地在子字符串数组中查找字符串的问题是如何产生的呢？解决方法是什么呢？

在上述内容中，提到了解决问题的两个步骤。

首先，将数组hasystack按照字符串长度的降序进行排序。这样做的目的是为了优化查找过程。排序后的数组中，较长的字符串会排在前面，这样在比较过程中能够更快地排除不匹配的情况。如果不进行排序，查找的时间复杂度是O(n)，而经过排序后，时间复杂度变为O(n log n)，能够更高效地完成查找操作。

接下来，按照从右到左的顺序，比较前缀与目标字符串needle。如果前缀的长度为5个字符，则先比较prefix[4]和needle[4]，然后比较prefix[3]和needle[3]，以此类推。通过这种方式，可以快速地排除不匹配的情况，并且能够优先找到最长的匹配字符串。

需要注意的是，排序数组并不是必需的。如果没有要求优先找到最长的匹配字符串，那么根据具体情况，排序可能会有利也可能没有帮助。

通过以上方法，可以高效地在子字符串数组中查找目标字符串。

0