递归的索引

Question

你好同事，我有一个关于递归的问题，我不明白，是C++和全新的。因此，对于此练习，我正在完成，我需要：1.向用户询问一个字符串2.要求用户输入一个字符串，以便在输入的第一个字符串中进行搜索。 3.如果发现它，报告和索引字符串。例如，用户输入字符串“搜索我”，搜索的字符串是“我”，索引将返回“7”。我在这一点上投入了一些关于如何完成它的帮助，任何帮助将不胜感激。这是我迄今为止的代码。 for循环中的内容并不完整，仅供参考。

int index_of(string stringToSearchIn, string stringToSearchFor, int index) 
{ 

if (stringToSearchIn.length() < stringToSearchFor.length()) 
{ 
    cout << "Your string cannot be found." << endl; 
    system("PAUSE"); 
    return OUTLIER; 
} 
else 
{ 
    bool found = true; 
    for (int i = ZERO; i < stringToSearchFor.length; i++) 
    { 
     found = found && stringToSearchIn(i) == stringToSearchFor(i); 
    } 
    return index; 
} 

return index_of(stringToSearchIn.substr(INCREASE), stringToSearchFor, index++); 
} 

int main() 
{ 
//Initializing values 
string userString; 
string userSearch; 
int userIndex = 0; 

//Asking for user input for string 
cout << "This program will find the occurence of one string inside of another." << endl; 
cout << "Enter the string to be searched: " << userString; 
//Getting the string 
getline(cin, userString); 

//Asking for user input for search input 
cout << "Now enter the string you want to search for: " << userSearch; 
//Getting the string 
getline(cin, userSearch); 

//Displaying results 
cout << "The index of the substring is = " << index_of(userString, userSearch, userIndex); 

//Keeping console window open until key press 
system("PAUSE"); 
return ZERO; 
} 

Answer 1

赶上。:)

#include <iostream> 

size_t index_of(const char *s, const char *t) 
{ 
    const char *p = s; 
    const char *q = t; 

    while (*q && *p == *q) ++p, ++q; 

    if (*q == '\0') 
    { 
     return 0; 
    } 
    else if (*p == '\0') 
    { 
     return -1; 
    } 
    else 
    { 
     size_t n = 1 + index_of(s + 1, t); 
     return n == 0 ? -1 : n; 
    } 
} 

int main() 
{ 
    const char *s = "Search me"; 
    const char *t = "me"; 

    size_t n = index_of(s, t); 

    if (n != -1) 
    { 
     std::cout << "string " << t << " is found at position " << n << std::endl; 
    } 
    else 
    { 
     std::cout << "string " << t << " is not found" << std::endl; 
    } 

    return 0; 
} 

输出是

string me is found at position 7 

对于其他字符串我没有测试的功能。:)

对于类型的对象std::string你可以称之为

size_t n = index_of(s.c_str(), t.c_str()); 

否则，如果你想为std :: string类型的对象编写一个类似的递归函数，那么你需要添加一个静态局部变量来保持源字符串中的当前位置或者为索引添加一个或多个参数，或者使用成员函数substr。

另外我的建议是不使用清单常量零为零。在我看来，这是一种糟糕的编程风格。它只会让读者感到困惑，因为ZERO可以是任何东西，包括一些用户定义的类。

例如（未经测试）

#include <iostream> 
#include <string> 

std::string::size_type index_of(const std::string &s, const std::string &t) 
{ 
    static std::string::size_type pos; 

    if (s.size() < t.size()) return std::string::npos; 

    if (s.compare(pos, t.size(), t) == 0) return 0; 

    ++pos; 

    std::string::size_type n = index_of(s, t); 

    --pos; 

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


int main() 
{ 
    std::string s = "Search me"; 
    std::string t = "me"; 

    std::string::size_type n = index_of(s, t); 

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


    return 0; 
} 

至于你的功能实现那看起来就例如下面的方式

#include <iostream> 
#include <string> 

std::string::size_type index_of(const std::string &stringToSearchIn, 
           const std::string &stringToSearchFor, 
           std::string::size_type index) 
{ 
    if (stringToSearchIn.length() < stringToSearchFor.length() + index) 
    { 
     return std::string::npos; 
    } 
    else if (stringToSearchIn.compare(index, 
             stringToSearchFor.length(), 
             stringToSearchFor) == 0) 
    { 
     return index; 
    } 
    else 
    { 
     std::string::size_type n = 
      index_of(stringToSearchIn, stringToSearchFor, ++index); 
     return n == std::string::npos ? std::string::npos : n; 
    } 
} 

int main() 
{ 
    std::string s = "Search me"; 
    std::string t = "me"; 

    std::string::size_type n = index_of(s, t, 0); 

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

    return 0; 
}