c++ - 学习递归 : How can I locate a substring index within a string without using find?

Question

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

Answer 1

有几个问题——一些是小问题，一些是非常重要的问题。

1. 您有两个变量，start 和 index，用于指示“当前位置”，但一个就足够了。

2. index 只能是 0 或 1。因此，按照目前的写法，您可以轻松摆脱 index 和 start 完全。

3. 重要提示:在最后的递归期间，当到达字符串末尾时，您将 -1 返回到之前的递归调用。然后，由于递归调用的完成方式，您添加 1 并将其返回到上一个调用，依此类推。最后返回的值是-1加上字符串的长度。这就是为什么你会得到奇怪的结果。

4. 这个对比

   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;
}