我有一个递归函数来查找字符串中子字符串的起始索引。我正在学习使用递归,因此不允许使用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;
}

最佳答案

有几个问题-一些小问题,一些非常重要的问题。


您有两个变量startindex表示“当前位置”,但是一个就足够了。
index只能是0或1。因此,按照当前的编写方式,您可以轻松地完全摆脱indexstart
重要说明:在最终递归过程中,如果到达字符串的结尾,则将-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;
}

10-05 21:28
查看更多