String within a string recursive function error

Question

I have a problem with a recursive function I'm trying to write. The purpose of the function is to find a string within a string and then return the index at which the second string is located inside the first using recursion.

I am able to do this. The problem comes when the second string isn't contained in the first string. I'm want to out to the user that the second string was not found. I can't get it to relay that message.

int index_of(string s, string t){
  int len1 = s.length(), len2 = t.length(), index = 0;
  if (len1==len2){
     if (s.substr(index, len2) == t){
       return index;
     }else{
       return -1;
     }
  else{
    index++;
    return index_of(s.substr(index, len1),t)+index;
  }
}

int main(){ 
  string strOne = "", strTwo = "";
  cout << "This program will find the ocurrence of one string within        another.\n\nEnter the string to be searched:\t";
  getline(cin, strOne);
  cout << "\nNow enter the string you want to search for:\t";
  getline(cin, strTwo);
  int index = index_of(strOne, strTwo);
  if (index == -1){
    cout << "\nThe second string cannot be found. Sorry!\n\n";}
  else{
    cout << "\nThe index of the substring is:\t" << index << "\n\n";
  }
  system("PAUSE");
  return 0;
}

Any help would be greatly appreciated! :)

You shouldn't use recursive function for that purpose. On large strings you get stack overflow. — Heavy, Nov 10 '14 at 06:53
I am not a c++ programmer, but can you compare strings like this: 'str1 == str2'? Don't you have to use strcmp(str1, str2)? I think the first option only compares the addresses of the strings? — linluk, Nov 10 '14 at 07:02
possible duplicate of [How to recursively compare vectors?](http://stackoverflow.com/questions/26353067/how-to-recursively-compare-vectors) — smac89, Nov 10 '14 at 07:17
What do you want the function to do if `s` does not contain `t`? Write a message to `stdout`? Throw an exception? Return -1? — Beta, Nov 10 '14 at 07:17
2 problems. 1) the -1 is going to be increased by the caller. 2) the length comparison should be `>=` not `==` — sp2danny, Nov 11 '14 at 07:01

score 0 · Answer 1 · edited May 23 '17 at 10:33

0

If first string doesn't contain the second, index being incremented infinitely making string s zero length. So you have to check, whether the first string is shorter than the second. If so, it doesn't contain the substring.

  if (len1 < len2){
    // first string doesn't contain the second
    return -2;
  }else if (len1==len2){
    ...

But you shouldn't use recursive function here at all. Also there is a built-in function find in string: Check this question: Check if a string contains a string in C++

edited May 23 '17 at 10:33

Community

1
1

answered Nov 10 '14 at 08:07

Heavy

1,861
14
25

`std::find` looks for a single character. For searching for a substring, you need `std::search`. – James Kanze Nov 10 '14 at 09:27
Not exactly, there are several overloads: http://www.cplusplus.com/reference/string/string/find/ – Heavy Nov 10 '14 at 09:42
But that's not what you said. The only interpretation I can put on "built-in function" is "standard library function", not "member function". – James Kanze Nov 10 '14 at 09:56
Yeah, by "built-in function" I ment that this function already exists in `std::string`. – Heavy Nov 10 '14 at 10:40

score 0 · Answer 2 · answered Nov 10 '14 at 09:54

There are a number of problems in the code you've posted, first and formost, that it won't compile, because you don't define index in index_of. And of course, you only do the comparison whenthe two strings are the same length. But it's hard to figure out what the comparison is that you're trying to do, since you take a substring based on the undefined variable index; if index is 0, the there is no point in taking the substring, and if index isn't 0, then s.substr( index, len2 ) == t can never be true (since you only enter this branch if both s and t have the same length.

What you really have to do is start by defining in plain English what the function should do:

If s is shorter than t, no match is possible, so you return -1.
Otherwise, if the start of s is equal to t, you return the current index.
Otherwise, you recurse on the substring of s, removing the first character (and incrementing index).

Of course, you also need to maintain index somewhere; in classical recursion, this would be as an additional function argument.

Frankly, I would not construct all of those substrings. It's far more idiomatic in C++ to use iterators. And I would wrap the recursive function in a non-recursive one, so that the user wouldn't have to pass in any extra arguments: the user might call something like:

int
indexOf( std::string const& text, std::string const& target )
{
    return indexOf( 0, text.begin(), text.end(), target );
}

Or, without passing the extra argument:

int
indexOf( std::string const& text, std::string const& target )
{
    std::string::const_iterator results 
            = search( text.begin(), text.end(), target );
    return results == text.end()
        ?  -1
        :  results - text.begin();
}

(I'm assuming that this is homework; one wouldn't normally use recursion for a problem like this. Otherwise, of course, just call std::search in the second version, and the job is done. Or text.find( target ), which returns almost exactly what you want.)

String within a string recursive function error

2 Answers2