Рекурсивных получить индекс начала подстроки в строке в C++

Question

Учитывая функцию:

int getIndex(string mystring, string substring); 

Как найти индекс mystring где substring начинается, если есть один? Я не хочу использовать функцию по умолчанию find, я хочу сделать свой собственный (на C++). Метод find возвращает true, если существует такая подстрока.

У меня есть следующие мысли до сих пор:

int getIndex(string mystring, string substring) 
{ 
    if(find(mystring, substring)) 
     return counter(); 
return -1; 
} 
int counter() 
{ 
     int count; //I'm not sure how to use this value without a global 
        //variable or variable declared in main() 
     ++count; 
} 

Answer 1

Создайте перегруженную функцию, которая выполняет реальную работу и сделает ее рекурсивной. Вызвать вторую функцию из первой с начальным индексом.

int getIndex(char const* mystring, size_t len1, 
      char const* substring, size_t len2, int index) 
{ 
    if (len1 < len2) 
    { 
     return -1; 
    } 

    if (strncmp(mystring, substring, len2) == 0) 
    { 
    return index; 
    } 

    return getIndex(mystring+1, len1-1, substring, len2, index+1); 
} 

int getIndex(string mystring, string substring) 
{ 
    return getIndex(mystring.c_str(), mystring.size(), 
        substring.c_str(), substring.size(), 
        0); 
} 

Answer 2

как о переборе строки, останавливаться каждый раз, когда персонаж соответствует первому символу сверхнизкочастотной строки, а затем посмотреть, если счетчик достаточно мал для подстроки чтобы соответствовать, и если да, итерации в символе подкопа по символу, чтобы найти совпадение?

Answer 3

Функция может быть записана следующим образом

std::string::size_type GetIndex(const std::string &myString, 
           const std::string &subString) 
{ 
    if (myString.size() < subString.size()) return std::string::npos; 
    if (myString.substr(0, subString.size()) == subString) return 0; 

    std::string::size_type n = GetIndex(myString.substr(1), subString); 

    return (n == std::string::npos) ? std::string::npos : n + 1; 
}         

Вот это demonstartive программу

#include <iostream> 
#include <string> 

std::string::size_type GetIndex(const std::string &myString, 
           const std::string &subString) 
{ 
    if (myString.size() < subString.size()) return std::string::npos; 
    if (myString.substr(0, subString.size()) == subString) return 0; 

    std::string::size_type n = GetIndex(myString.substr(1), subString); 

    return (n == std::string::npos) ? std::string::npos : n + 1; 
}         

int main() 
{ 
    std::string::size_type n = GetIndex("Hello World", "World"); 

    if (n != std::string::npos) 
    { 
     std::cout << "The substring is found at position " << n << std::endl; 
    } 
    else 
    { 
     std::cout << "The substring is not found" << std::endl; 
    } 

    n = GetIndex("Hello C", "C++"); 

    if (n != std::string::npos) 
    { 
     std::cout << "The substring is found at position " << n << std::endl; 
    } 
    else 
    { 
     std::cout << "The substring is not found" << std::endl; 
    } 
}  

Его выход

The substring is found at position 6 
The substring is not found 

Если вы хотите, вы можете заменить тип std::string::size_type для int и std::string::npos для -1. :)