子串递归算法不起作用

Question

我是第一个C++类的编程学生,最近我们被鼓励编写一个简单的递归函数来查找给定字符串中第一次出现的子字符串.如果找到,则返回索引.如果未找到子字符串,则该index_of()函数应返回-1.我们鼓励使用一个辅助函数,它将索引作为其参数之一,这就是我尝试过的.

例如:

int index_of("Mississippi", "sip"); // this would return a 6

这应该是一个简单的练习,以帮助我们理解递归,并且不会被提交.我的教授说我们实际的递归赋值将更加复杂,这就是为什么我真的想要理解递归的简单用法.

我已经使用C风格的字符串和指针成功完成了这项工作,但没有使用C++ std :: string对象.我的节目中我做错了什么？我的教授表示我们应该能够在5分钟内轻松写出来,但我已经苦苦挣扎了两个小时.这是我到目前为止所做的:

int index_of(string s, string t)
{
    int index = 0;

    if (s[index] == NULL)
        return -1;
    else if (starts_with(s, t, ++index))
    {
        return index;
    }
    else 
        return index;
}

bool starts_with(string s, string t, int index)
{
    if (t[index] == NULL)
        return true;
    if ( s[index] == NULL || t[0] != s[index])
        return false;
    return starts_with(s, t, ++index);
}

如上所述,此函数始终返回index1.

Answer 1

int index_of(string s, string t)
{
    int index = 0;

    if (s[index] == NULL)

完全停止.这不是C++的字符串如何工作,如果你想使用它们,你必须解决这个问题.即使使用C风格的字符串,也不要使用NULL来表示ASCII空字符.它们共享一个名称但具有不同的用途,您不应该使用NULL来表示整数零(字符是整数类型,空字符是它们的零值).使用'\0'或只是if (s[index]).

但是,除非您知道索引有效,否则不允许索引std :: string.为此,请将索引与s.size()(并确保它大于或等于0)进行比较.即便如此,你在这里测试的是s是否为空,并且它有一个特殊的方法来做到这一点:

    if (s.empty())

继续:

    else if (starts_with(s, t, ++index))

内部表达式的增量和减量,特别是在这里,对于没有优势的初学者来说可能会让人感到困惑.它们的主要优点是代码简洁明了,但您必须先了解代码的主要部分,即使是经验丰富的程序员有时也会受益于更加冗长的代码.

有趣的是,Go的创作者,他们也参与了早期的C历史,甚至将表达式的增量转化为声明,我相信清晰度是其中很大一部分原因.

从最开始

您想要使用此签名实现一个函数:

int index_of(string haystack, string needle);
// returns the index of needle in haystack, if found
// otherwise returns -1

我故意将这些注释包含在签名中:它们是此功能的公共接口的一部分.更好的参数名称也增加了清晰度

确定您需要考虑的案例:

• 针是空的(你可以用多种方式处理)
• haystack为空:返回-1
• 在这一点上,我们知道干草堆和针都不是空的
• 留下两个案例是算法的关键:
  • haystack的第一个字符与针的第一个字符不匹配
  • 有一个匹配的第一个字符

当第一个字符匹配时,您有两个子案例:

• 针中没有更多字符:匹配找到
• 还有更多字符:继续检查

我把它们写成递归算法,它接收每个字符串(和子字符串)的"新副本"而不是使用索引.但是,您可以通过将"第一个字符"更改为"当前字符"来转换为使用索引,对于"空"条件也是如此.在这种情况下你会想要使用两个索引(并且尝试只使用一个索引可能是你到目前为止的主要绊脚石),除非你有一个帮助功能来比较子串(虽然我不确定你的教授是否有一个与此评论分开的意图).

将上述散文直接翻译成代码:

int index_of(string haystack, string needle) {
  if (needle.empty()) return 0;
  // this implementation considers empty substrings to occur at the start of any
  // string, even an empty haystack; you could also make it an error to call
  // index_of when needle is empty, or just return -1

  if (haystack.empty()) return -1;

  assert(!needle.empty() && !haystack.empty()); // I wouldn't normally include
  // this, since we just checked these conditions, but this is the "at this
  // point we know both haystack and needle are not empty" that I mentioned

  if (haystack[0] != needle[0]) {
    // mark A, see below
    int index = index_of(haystack.substr(1), needle);
    return index != -1 ? index + 1 : index;
  }

  if (needle.length() == 1) return 0; // found complete match
  // note the way I chose to handle needle.empty() above makes this unnecessary

  // mark B, see below    
  // partial match (of the first character), continue matching
  int index = index_of(haystack.substr(1), needle.substr(1)); // strip first
  return index == 0 ? 0 : -1;
  // must check index == 0 exactly, if -1 then we must return that, and if not 0
  // then we've found a "broken" needle, which isn't a real match
}

破碎的针注释暗示了代码的低效率,因为它将递归调用分为两类:必须在1处(在切入子字符串后为0),在标记B处匹配,并且可以在任何地方匹配,在标记A处.可以使用辅助函数改进这一点,我将使用std :: string的operator == overload(在haystack的子字符串上运行).这产生了经典的"天真的strstr " 的递归等价物:

int index_of(string haystack, string needle) {
  if (needle.empty()) return 0;
  if (haystack.empty()) return -1;
  if (haystack.substr(0, needle.length()) == needle()) {
    return 0;
  }
  int index = index_of(haystack.substr(1), needle);
  if (index != -1) index++;
  return index;
}

当使用带有string :: compare的haystack索引作为帮助程序时,不需要针索引:

// might not be exposed publicly, but could be
int index_of(string const& haystack, int haystack_pos, string const& needle) {
  // would normally use string const& for all the string parameters in this
  // answer, but I've mostly stuck to the prototype you already have

  // shorter local name, keep parameter name the same for interface clarity
  int& h = haystack_pos;

  // preconditions:
  assert(0 <= h && h <= haystack.length());

  if (needle.empty()) return h;
  if (h == haystack.length()) return -1;
  if (haystack.compare(h, needle.length(), needle) == 0) {
    return h;
  }
  return index_of(haystack, h+1, needle);
}

int index_of(string haystack, string needle) {
  // sets up initial values or the "context" for the common case
  return index_of(haystack, 0, needle);
}

请注意,此版本是尾递归的,但这仍然是一种天真的算法,并且存在更高级的算法.

如果我有更多的时间,我会写一封较短的信.
    - 西塞罗

你已经说过这对你很有帮助,但是,即使有我刚才包含的其他例子,我似乎也缺乏.在我看来,子串搜索不是一个很好的递归练习,这可能就是原因.

Answer 2

您的代码归结为此

int index_of(string s, string t)
{
    int index = 0;

    //if (s[index] == NULL)
    //    return -1;
    ++index // from this: else if (starts_with(s, t, ++index))
    //{
    //    return index;
   // }
   //else 
        return index;
}

所以,是的,它总是返回1

index在递归starts_with函数内继续递增,但更改后的值永远不会使其返回为返回值.