3

假设我有一些词 AB，AAB，AA。

AB 不是 AAB 的前缀，但 AA 是 AAB 的前缀，因为如果我只是在 AA 的末尾添加 B，它将变成 AAB，这对于 AB 是不可能的。

那么，C++（STL）中是否有任何功能，以便我可以确定两个单词是否是另一个单词的前缀？

谢谢。

4

9 回答 9

9 
template<class C, class T, class A>
bool starts_with(std::basic_string<C,T,A> const& haystack,
                 std::basic_string<C,T,A> const& needle)
{
  return needle.length() <= haystack.length() &&
    std::equal(needle.begin(), needle.end(), haystack.begin());
}

请注意，长度检查不是过早优化，它需要满足 std::equal 的前提条件。

于 2010-03-20T10:57:59.283 回答
5 
std::string full = "AAB", pre= "AA";
bool prefixed = full.find( pre ) == 0;

或者怎么样：

bool prefixed =  full.compare( 0, pre.size(), pre ) == 0;
于 2010-03-20T10:55:20.200 回答
3 
std::string full = "AAB", lookfor = "AA";
const bool isprefixmatch = (full.substr(0,lookfor.lenght())==lookfor);
于 2010-03-20T10:53:06.963 回答
2

这个答案适用于 C 和 C++，不需要 STL。

// test if string2 a prefix of string1
// inputs must be non NULL
// returns TRUE if string2 is a prefix, otherwise FALSE

int isAPrefix(const char *string1,
              const char *string2)
{
    return (strncmp(string1, string2, strlen(string2)) == 0);
}
于 2010-03-20T11:36:33.667 回答
2

如果您已经依赖于 Boost，那么boost::algorithm::starts_with.

int main()
{
    std::cout << boost::algorithm::starts_with("abba", "ab"); // true
    std::cout << boost::algorithm::starts_with("abba", "ba"); // false
    return 0;
}

每当您发现std::string缺少所需的字符串操作方法时，请查看Boost String Algorithms库。

于 2010-03-20T16:21:34.780 回答
1

使用find字符串的方法。检查它返回的索引是否在字符串的开头。

于 2010-03-20T10:53:15.700 回答
1

http://www.cplusplus.com/reference/string/string/是查找此类内容的好地方。花 10 分钟时间熟悉这些功能，因为它们中的大多数都非常有用。

您可以使用 find 在另一个字符串中的任何位置查找文本，但 find_first_of 可能更合适（并与后缀进行比较）。否则要查找后缀， find_last_of 将是合适的。

于 2010-03-20T10:57:21.740 回答
0

我认为，您的问题的真正答案是使用前缀树。接受的答案算法将完成这项工作，但您必须检查您的词组中的每个其他词的前缀词，这在时间上是线性的。对所有单词都这样做（假设你想得到所有作为其他单词前缀的单词）并且你手上有 O(n^2) 复杂度。一个词是否是另一个词的前缀的简单检查与词的长度成线性关系。

使用前缀树将以对数时间回答您的第一个问题，第二个问题以线性时间回答。检查一个单词是否是前缀只是从根向上漫步，直到在树中找到单词并且最后一个节点不是叶子（意味着存在扩展它的更长单词） - 受树的高度限制。另一方面，遍历树并在最后一个节点不是叶子的每个步骤上写下当前单词将产生所有前缀单词的列表。树遍历是在线性时间内完成的，因为您只会访问每个节点一次。

于 2010-03-20T11:30:12.163 回答
0

如果您只是发现一个字符串或子字符串是 u 以外的前缀，则可以简单地使用这个 fn

 std::size_t found = str1.find(str2); //returns position of str2 in str1 (if found==0) than it is prefix else not.

如果它不存在，则它返回一个垃圾值，如果 U 对 no 执行相同操作。字符串，想要快速完成，你必须使用 TRIE。

于 2018-03-18T21:00:18.753 回答