Рекурсивный алгоритм подстроки, не работающий

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

Я специально включил эти комментарии с подписью: они являются частью открытого интерфейса для этой функции. Более точные названия параметров также увеличивают ясность.

Определите случаи, которые вам необходимо учитывать:

• игла пуста (вы можете справиться с этим несколькими способами)
• стог сена пуст: return -1
• на данный момент мы знаем, что стог сена и иголка нет empty
• , что оставляет два случая, которые являются сутью алгоритма:
  • первый символ стога сена не соответствует первому символу иглы
  • есть совпадение первый символ

И когда есть совпадение первого символа, у вас есть два подварианта:

• больше нет символов в игле: совпадение найдено
• есть больше символов: продолжить проверку

Я написал их как рекурсивный алгоритм, который получает «новые копии» каждой строки (и подстроки) вместо использования индексов. Однако вы можете преобразовать для использования индексов, изменив «первый символ» на «текущий символ», и аналогично для «пустых» условий. В этом случае вы захотите использовать два индекса (и попытка использовать только один, возможно, до сих пор была для вас серьезным камнем преткновения), если у вас нет вспомогательной функции для сравнения подстрок (хотя я не уверен, что у вашего профессора были отдельные намерения с этим комментарием).

Прямой перевод вышеупомянутой прозы в код:

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 оператор == overload (работающий с подстрокой стога сена).Это дает рекурсивный эквивалент классического "наивного 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 в качестве помощника, поэтому индекс иглы не требуется:

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

Замечание эта версия хвостовая рекурсивная, но это все еще наивный алгоритм, и существуют более продвинутые .

Если бы у меня было больше времени, я бы написал более короткое письмо.
- Цицерон

Вы сказали, что это очень помогло вам, но даже с дополнительными примерами, которые я только что привел, мне кажется, что этого не хватает. На мой взгляд, поиск подстроки - не лучшее упражнение для рекурсии, и, возможно, именно поэтому.