在字符串中搜索模式

Question

我真的很难得到递归,但我尝试递归来匹配字符串中的模式.

假设我有一个极客的字符串极客,我有一个模式eks匹配.我可以使用很多方法,如正则表达式,查找字符串类的方法,但我真的想通过递归来做这件事.

为实现这一点,我试过这段代码:

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")

返回？那么,根据文档,你会得到积极的东西,因为"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. comparesubstr由于它的算法需要使用.编写自己不需要的比较函数substr.
2. 有很多复制正在进行中.你能摆脱那个吗？
3. 该for循环是错误的.为什么？