我是第一个 C++ 类(class)的编程学生，最近我们被鼓励编写一个简单的递归函数来查找给定字符串中子字符串的第一次出现。如果找到，它返回索引。如果未找到子字符串，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);
}

如所写，此函数始终返回 1 的 index。

最佳答案

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))

递增和递减内部表达式，尤其是这里，可能会让初学者感到困惑，没有任何优势。它们的主要优点是代码简洁明了，但您必须先理解代码的主要部分，即便如此，有经验的程序员有时也会从稍微冗长一点中受益。

有趣的是，同样参与早期 C 历史的 Go 的创造者甚至将 increment 从表达式变成了语句，我相信清晰度是很大一部分原因。

从头开始

你想用这个签名实现一个函数:

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

我特意将这些注释包含在签名中:它们是此功能的公共(public)接口(interface)的一部分。更好的参数名称也会增加清晰度。

确定您需要考虑的情况:

• 针是空的(您可以通过多种方式处理)
• 干草堆是空的:返回-1
• 此时我们知道大海捞针和针头都不是空的
• 剩下的两种情况是算法的关键:
  • haystack的第一个字符与needle的第一个字符不匹配
  • 第一个字符匹配

当第一个字符匹配时，您有两个子情况:

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

我将这些编写为递归算法，它接收每个字符串(和子字符串)的“新拷贝”而不是使用索引。但是，您可以通过将“第一个字符”更改为“当前字符”来转换为使用索引，对于“空”条件也是如此。在那种情况下你会想要使用 两个 索引(到目前为止，尝试只使用一个可能是你的主要障碍)，除非你有一个帮助函数来比较子串(虽然我'我不确定你的教授是否对这个评论有单独的意图)。

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

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 处匹配，并且可以在任何地方匹配，在标记处答:我们可以用辅助函数改进它，为此我将使用 std::string 的 operator== 重载(在 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 索引作为助手时，不需要 needle 索引:

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

注意这个版本是尾递归的，但这仍然是一个简单的算法和更高级的算法 exist .

If I had more time, I would have written a shorter letter.
    — Cicero

您说过这对您有很大帮助，但是，即使有我刚刚包含的其他示例，我似乎也缺乏。在我看来，子字符串搜索不是一个好的递归练习，这可能就是原因。

关于c++ - 子串递归算法不起作用，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2308696/