我有一个递归函数来查找字符串中子字符串的起始索引。我正在学习使用递归,因此不允许使用find函数。我相信我已经满足了大多数条件。该函数应该在字符串中找到正确的索引。如果为空,则返回-1。
这是真正的问题。如果我输入字符串“ nothing”并搜索“ jax”,则不会返回-1。我不明白为什么。有什么帮助吗?这是代码:
用户将输入字符串s和t传递到下面:
int index_of(string s, string t)
{
int start = 0;
int len2 = t.length();
int index = 0;
if (s == "")
{
return -1;
}
else if (s.substr(1).length() <= t.length())
{
return -1;
}
else if ( s.substr(start, len2) == t)
{
return index;
}
else
{
index ++;
return index + index_of(s.substr(1), t);
}
return -1;
}
最佳答案
有几个问题-一些小问题,一些非常重要的问题。
您有两个变量start
和index
表示“当前位置”,但是一个就足够了。index
只能是0或1。因此,按照当前的编写方式,您可以轻松地完全摆脱index
和start
。
重要说明:在最终递归过程中,如果到达字符串的结尾,则将-1
返回上一个递归调用。然后,由于完成了递归调用的方式,您添加了1
并将其返回到上一个调用,依此类推。最后返回的值是-1
加上字符串的长度。这就是为什么您得到奇怪的结果的原因。
比较
if (s.substr(1).length() <= t.length())
没有多大意义。
考虑到所有这些,这是一个改进的版本:
#include <iostream>
#include <string>
int index_of(
const std::string &s,
const std::string &t,
const size_t index)
{
int len2 = t.length();
if ((s.length() - index) < t.length())
return -1;
else if (s.substr(index,len2) == t)
return index;
else
return index_of(s,t,index + 1);
return -1;
}
/** Overloading, so you can call index_of with just
two arguments */
int index_of(const std::string &s, const std::string &t)
{
return index_of(s,t,0);
}
/** Some test cases. */
int main()
{
std::cout << index_of("hello","ello") << std::endl;
std::cout << index_of("nothing","jax") << std::endl;
std::cout << index_of("hello","llo") << std::endl;
std::cout << index_of("hello","lo") << std::endl;
std::cout << index_of("hello","o") << std::endl;
std::cout << index_of("hello","hel") << std::endl;
}