在 C++ 中递归查找字符串中的字符串

Question

(C++) 给定 myString，我想检查 myString 是否包含子字符串。到目前为止，这是我所拥有的，但只有 returns 如果字符串以子字符串开头，它才为真。

 bool find(string myString, string substring)
{
    if(mystring.length() < substring.length())
    { 
        return false;
    }
    if(mystring == substring)
    {
        return true;
    }
    for(int i = 0; i < substring.length() - 1 ; ++i)
    {
        if(mystring.at(i) == substring.at(i))
           {
               continue;
           }
        else
        {
            string string2 = mystring.substr(1, mystring.length() - 1);
            return find(string2, substring); 
        }
        return true;
    }
    return false;
}

这个函数有什么问题？

Answer 1

在对 find 的递归调用之前，您缺少 return。就目前而言，它会落到最后的 return false。

此外，if (mystring == substring) 应该检查 mystring 是否以 substring 开头，而不是完全相等。

Answer 2

首先，这是昂贵的，因为 substr 中的内存副本。

其次，您还没有检查子字符串长度 > 0。

第三，如果您已经完成其他检查（包括子字符串长度 > 0），"else if" 检查 mystring.length > 0 是多余的。

现在开始你的核心逻辑。在递归中，你的起点永远不会移动，所以你被束缚在起点上。您需要做的是从位置 1 开始，并在每次递归时递增 start，并使用 substr 提取从 "start" 到 "start + substring.length" 的子字符串。这样你就可以从头开始，继续前进，并检查正确的长度。您也可以从末尾开始（如您所愿）然后向后移动，您需要做的是：找到 sart 位置（结束位置减去子字符串的长度），并在调用之前检查起始位置是否不小于零函数递归。

Answer 3

您只是删除了 myString 最左边的字符，然后将其余字符与您的 substring 进行比较。显然，这在一般情况下是行不通的，当您的 substring 位于 myString.

中间的某个位置时

在每次迭代中尝试比较的不是整个 myString，而是它的前 substring.size() 个字符。这应该可以解决您的问题。

Answer 4

Here's what I have so far, but it only returns true if the string begins with the substring.

find("foo", "f") 也失败了。

要了解原因，请向函数添加一些测试输出：

bool find(string myString, string substring)
{
    std::cout << myString << ", " << substring << "\n";
    // ...
}

它将打印：

foo, f
oo, f
o, f

你明白为什么这行不通了吗？您只需继续删除第一个字符，直到只有最后一个字符与要找到的子字符串进行比较。

但即使 find("foo", "o") 也失败了：

foo, o
oo, o
o, o

那是因为这一行：

   find(string2, substring);

你没有return递归调用的结果。

考虑到所有因素，我认为您这里的算法是错误的。它根本无法按照您编写代码的方式工作。

其他一些观察结果：

    int start = 1;
    int end = (int) myString.length() - 1;

这不是很好的风格。由于历史原因，std::string 的大小是无符号的，并且您正在使用 C 风格的转换，其中应该首选 static_cast。你应该在这里使用 std::string::size_type，因为它只是一段内部实现代码，你从转换到 int.

中没有任何收获。

   string string2 = myString.substr(start, end);

substr的第二个参数定义子字符串的长度，而不是最后一个字符的索引。 end 听起来您将该值用作最后一个字符的索引。看看 http://en.cppreference.com/w/cpp/string/basic_string/substr.

Answer 5

检查此功能，它基于您的代码，删除了额外的代码并修复了错误。

为了提高效率我也改了签名获取const引用

bool find(const string& myString, const string& substring)
{
    if(myString.length() < substring.length()){ 
        return false;
    }
    else if(myString.substr(0,substring.size()) == substring){
        return true;
    }
    else if (myString.length() > substring.length()){
        return find(myString.substr(1), substring); 
    }
    else{
        return false; 
    }
}

Answer 6

首先函数可以写得简单一些。例如

bool find( const std::string &myString, const std::string &subString )
{
    return 
    ( myString.substr( 0, subString.size() ) == subString ) ||
    ( subString.size() < myString.size() && find( myString.substr( 1 ), subString ) );
}

这是一个演示程序

#include <iostream>
#include <iomanip>
#include <string>

bool find( const std::string &myString, const std::string &subString )
{
    return 
    ( myString.substr( 0, subString.size() ) == subString ) ||
    ( subString.size() < myString.size() && find( myString.substr( 1 ), subString ) );
}

int main()
{
    std::cout << std::boolalpha << find( "Hello World", "World" ) << std::endl;
    std::cout << std::boolalpha << find( "Hello C", "C++" ) << std::endl;
}

程序输出为

true
false

至于你的函数，那么它 return 只有在两个字符串具有相同长度且彼此相等的情况下才为真

if(myString == substring){
        return true;
    }

如果 myString.length() > substring.length() 函数 return 什么都没有

else if (myString.length() > substring.length()){
    int start = 1;
    int end = (int) myString.length() - 1;
    string string2 = myString.substr(start, end);
    find(string2, substring); 
}

我想你是说

    return find(string2, substring);

在此代码段中。

编辑： 我看到您更改了 post 中的函数代码。但无论如何这个代码片段

for(int i = 0; i < substring.length() - 1 ; ++i)
{
    if(mystring.at(i) == substring.at(i))
       {
           continue;
       }
    else
    {
        string string2 = mystring.substr(1, mystring.length() - 1);
        return find(string2, substring); 
    }
    return true;
}

没有意义。

在 C++ 中递归查找字符串中的字符串

Recursively find a string within a string in C++

c++

string

recursion

substring