BOTJr. BOTJr. - 2 months ago 8
C++ Question

searching pattern in a string

I am really having a hard time getting recursions but i tried recursion to match a pattern inside a string.

Suppose i have a string geeks for geeks and i have a pattern eks to match.I could use many methods out there like regex, find method of string class but i really want to do this thing by recursions.

To achieve this i tried this code:

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()));
}


Output :

enter image description here

Desired Ouput :

pattern at 2
pattern at 12


What could i be doing wrong here and what would be a good way to do this with recursions?

I understood a lot of topics in cpp but with recursions , i know how they work and even with that whenever i try to code something with recursions , it never works.Could there be any place that could help me with recursions as well?

Answer

You will never get pattern at 2, since compare doesn't work like that. Ask yourself, what will

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

return? Well, according to the documentation, you will get something positive, since "eks for geeks" is longer than "eks". So your first step is to fix this:

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

Next, we have to recurse. But there's something off. i should be the current position of your "cursor". Therefore, you should advance it:

  i = i + 1;

And if we reduce the length of the string in every iteration, we must not test i < str.length, otherwise we won't check the later half of the string:

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

Before we actually compile this code, let's reason about it:

  • we have a substring of the correct length for comparison with "eks"
  • we never use i except for the current position
  • we advance the position before we recurse
  • we "advance" the string by removing the first character
  • we will end up with an empty string at some point

Seems reasonable:

#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;
}

Output:

pattern at: 2
pattern at: 12

However, that's not optimal. There are several optimizations that are possible. But that's left as an exercise.

Exercises

  1. compare needs to use substr due to it's algorithm. Write your own comparison function that doesn't need substr.
  2. There's a lot of copying going on. Can you get rid of that?
  3. The for loop was wrong. Why?
Comments