在字符串中搜索模式

Question

我真的很难获得递归，但我尝试递归匹配字符串内的模式。

假设我有一个字符串怪才怪才和我有一个模式EKS到match.I可以用许多方法有像正则表达式，找到字符串类的方法，但我真正想做的事情这件事通过递归。

要做到这一点我想这个代码：

void recursion(int i,string str) 
{ 
    if(!str.compare("eks")) 
     cout<<"pattern at :"<<i<<'\n'; 

    if(i<str.length() && str.length()-1!=0) 
     recursion(i,str.substr(i,str.length()-1)); 
} 

int main() 
{ 
    string str("geeks for geeks"); 

    for(int i=0;i<str.length();i++) 
     recursion(i,str.substr(i,str.length())); 
} 

输出：

期望输出继电器：

pattern at 2 
pattern at 12 

我应该怎么做是错在这里做什么会用递归来做这件事的好方法是什么？

我了解了cpp中的很多主题，但有了递归，我知道他们是如何工作的，甚至每当我尝试用递归编码时，它永远不会工作。可以有任何地方可以帮助我递归好？

Answer 1

你永远不会得到pattern at 2，因为compare不能这样工作。问问你自己，

std::string("eks for geeks").compare("eks") 

return？那么根据documentation，你会得到一些肯定的结果，因为"eks for geeks"比"eks"长。所以你的第一步是解决这个问题：

void recursion(int i, std::string str){ 
    if(!str.substr(0,3).compare("eks")) { 
    std::cout << "pattern at: " << i << '\n'; 
    } 

接下来，我们必须进行递归。但有些东西没有。 i应该是你的“光标”的当前位置。因此，你应该提前是：

i = i + 1; 

如果我们减少每次迭代的字符串的长度，我们绝不能测试i < str.length，否则我们不会检查字符串的后半段：

if(str.length() - 1 > 0) { 
    recursion(i, str.substr(1)); 
    } 
} 

在我们真正编译这段代码，让我们的原因吧：

• 我们有正确长度的字符串与"eks"
比较
• 我们从来不使用i除了当前位置
• 我们前进的位置，我们递归之前
• 我们“进步”的字符串通过删除第一个字符
• 我们将在某个时候
结束了一个空字符串

似乎是合理的：

#include <iostream> 
#include <string> 

void recursion(int i, std::string str){ 
    if(!str.substr(0,3).compare("eks")) { 
    std::cout << "pattern at: " << i << '\n'; 
    } 

    i = i + 1; 

    if(str.length() - 1 > 0) { 
    recursion(i, str.substr(1)); 
    } 
} 

int main() { 
    recursion(0, "geeks for geeks"); 
    return 0; 
} 

输出：

pattern at: 2 
pattern at: 12 

但是，这不是最佳的。有几种可能的优化。但这只是一个练习。

练习

1. compare需要使用substr，由于它的算法。编写你自己的比较功能，不需要substr。
2. 有很多复制正在进行。你能摆脱吗？
3. for循环错误。为什么？

Answer 2

递归函数不能进入循环。你有一些错误。试试这个代码。

void recursion(string str, string subStr, int i){ 
    if(str.find(subStr) != string::npos) { 
     int pos = str.find(subStr); 
     str = str.substr(pos + subStr.length(), str.length()-1); 
     cout << "pattern at " << (pos + i) << endl; 
     recursion(str, subStr, pos+subStr.length()); 
    } 
} 

int main(int argc, char** argv) { 
    string str("geeks for geeks"); 
    string subStr("eks"); 
    recursion(str, subStr, 0); 
    return 0; 
}