字符串递归函数中的字符串错误

Question

我试图编写的递归函数有问题。该函数的目的是在字符串中找到一个字符串，然后使用递归返回第二个字符串位于第一个字符串中的索引。

我能做到这一点。当第二个字符串不包含在第一个字符串中时，问题就出现了。我想告诉用户没有找到第二个字符串。我无法让它转达那条信息。

int index_of(string s, string t){
  int len1 = s.length(), len2 = t.length(), index = 0;
  if (len1==len2){
     if (s.substr(index, len2) == t){
       return index;
     }else{
       return -1;
     }
  else{
    index++;
    return index_of(s.substr(index, len1),t)+index;
  }
}
int main(){ 
  string strOne = "", strTwo = "";
  cout << "This program will find the ocurrence of one string within        another.nnEnter the string to be searched:t";
  getline(cin, strOne);
  cout << "nNow enter the string you want to search for:t";
  getline(cin, strTwo);
  int index = index_of(strOne, strTwo);
  if (index == -1){
    cout << "nThe second string cannot be found. Sorry!nn";}
  else{
    cout << "nThe index of the substring is:t" << index << "nn";
  }
  system("PAUSE");
  return 0;
}

如有任何帮助，我们将不胜感激！：）

Answer 1

您发布的代码中有很多问题，首先和formost，它不会编译，因为你没有定义CCD_ 2中的CCD_。当然，你只做当两个字符串长度相同时进行比较。但是很难弄清楚你试图进行的比较是什么执行，因为您使用基于未定义变量的子字符串index；如果index是0，那么取子字符串，如果index不是0，则s.substr( index, len2 ) == t永远不可能是真的（因为你如果s和index0的长度相同，则输入该分支。

你真正要做的是从用通俗的英语定义什么开始功能应该做：

• 如果s比t短，则不可能匹配，因此您return-1。

• 否则，如果s的起始值等于t，则返回当前索引。

• 否则，在s的子字符串上递归，删除第一个字符（以及递增index）。

当然，您还需要在某个地方维护index；在古典递归，这将作为一个额外的函数参数。

坦率地说，我不会构造所有这些子字符串。它远不止在C++中习惯使用迭代器。我会包装递归函数，这样用户就不必通过在任何额外的参数中：用户可能会调用类似的东西：

int
indexOf( std::string const& text, std::string const& target )
{
    return indexOf( 0, text.begin(), text.end(), target );
}

或者，在不传递额外参数的情况下：

int
indexOf( std::string const& text, std::string const& target )
{
    std::string::const_iterator results 
            = search( text.begin(), text.end(), target );
    return results == text.end()
        ?  -1
        :  results - text.begin();
}

（我假设这是家庭作业；通常不会使用递归对于这样的问题。否则，当然，只需拨打std::search在第二个版本中，工作完成了。或CCD_ 19，它几乎完全返回您想要的内容。）

Answer 2

如果第一个字符串不包含第二个字符串，则index_of0将无限递增，使string s的长度为零。所以你必须检查第一个字符串是否比第二个短。如果是，则它不包含子字符串。

  if (len1 < len2){
    // first string doesn't contain the second
    return -2;
  }else if (len1==len2){
    ...

但您根本不应该在这里使用递归函数。此外，在string中还有一个内置函数find：检查这个问题：检查字符串是否包含C++中的字符串