功能在C ++中寻找，如果一个字前缀

StackOverflow https://stackoverflow.com/questions/2482716

  •  21-09-2019
  •  | 
  •  

题

让说，我有一些话AB，AAB，AA。

AB不是前缀AAB AA但是因为AAB如果我只是在AA的端部就会变成AAB，这是不可能的AB添加乙前缀。

因此，有在C + +（STL）的任何函数，这样我可以确定的两个词如果一个前缀添加到另一个？

感谢。

有帮助吗？

解决方案 

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 ::相等的先决条件。

其他提示

std::string full = "AAB", pre= "AA";
bool prefixed = full.find( pre ) == 0;

或什么约：

bool prefixed =  full.compare( 0, pre.size(), pre ) == 0;

std::string full = "AAB", lookfor = "AA";
const bool isprefixmatch = (full.substr(0,lookfor.lenght())==lookfor);

此答案可与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);
}

如果您已经是依赖于升压，还有的 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缺少你需要一个字符串操作方法，检查出的升压字符串算法库。

使用一个字符串的find方法。检查它是否返回指数是在字符串的开头。

在真正回答您的问题，我想，是使用前缀树。接受的答案算法将做的工作，但你必须检查你的前缀wouldbe字每隔在你的词集这是在时间线。做到这一点对所有的话（说你想获得的所有那些前缀换言之的话），你有你的手为O（n ^ 2）的复杂性。 的简单的检查字是否是一个前缀到另一个上的字的长度是线性的。

使用前缀树将回答对数时间，第二你的第一个问题 - 线性。检查如果一个字是一个前缀只是几步从根本上去，直到你在树中找到的字和最后一个节点不是叶（意味着更长的词延长它的存在） - 由树的高度限制。遍历树，而另一方面，和为其最后一个节点不是叶将产生的所有前缀单词列表的每一步写下当前的单词。树遍历以线性的时间内完成，你将访问每个节点只一次。

如果你只是找到一个字符串或子是其他前缀不是U可以简单地用这个FN 

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

如果它不存在比它返回一个垃圾值 而如果ü做了不一样的。字符串和想的，你必须使用TRIE快捷的方式做。

不隶属于 StackOverflow
scroll top