Recursive Function

[patrickweiss52]

Hey guys,

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();
	int len2 = t.length();
	int 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 = "";
		string 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) //Fixed what MiiNiPaa pointed out
                {
			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! :)

[MiiNiPaa]

index is an int
'-1' is a character.
Use proper integral literal -1 instead

[patrickweiss52]

@miiNiPaa: Thanks, I was messing with that earlier. I fixed it. but I still don't get the if -1 out.
example: input 1: hello world input 2: patrick It says the index is 3... xD

[MiiNiPaa]

The problem is on line 19.

In your example you will reach recursion depth 5 before -1 is returned. Higher level function call returns -1 + 1 = 0, next returns 0 + 1 = 1, next 1 + 1 = 2 etc.
You need to either handle -1 return value separately or make latest function in chain responsible for return of complete index.

[patrickweiss52]

@MiiNiPaa: how would I implement that? I'm still really new.

What I mean is: I'm new to the concept of a recursive function. So Where would the hander for the return -1 go? after line 15?

[MiiNiPaa]

else{
	index++;
	int id = index_of(s.substr(index, len1),t);
	if (id == -1)
		return -1;
	return id + index;
	//return (id == -1)? -1 : id + index;
}

Alternative approach (tested, bug-free, consistent with standard library):

#include <iostream>
#include <string>


std::string::size_type index_of_impl(std::string s, std::string t, std::string::size_type ind)
{
    if (s.length() < t.length())
        return std::string::npos; //Consistent with standard library
    if (s.substr(0, t.length()) == t)
        return ind;
    return index_of_impl(s.substr(1, std::string::npos), t, ++ind);
}

std::string::size_type index_of(std::string s, std::string t)
{
    return index_of_impl(s, t, 0);
}

int main()
{
    std::cout << "This program will find the ocurrence of one string within another.\n\nEnter the string to be searched:\t";
    std::string strOne;
    std::getline(std::cin, strOne);
    std::cout << "\nNow enter the string you want to search for:\t";
    std::string strTwo;
    std::getline(std::cin, strTwo);
    std::string::size_type index = index_of(strOne, strTwo); //Use correct data type
    if (index == std::string::npos) {
        std::cout << "\nThe second string cannot be found. Sorry!\n\n";
    } else {
        std::cout << "\nThe index of the substring is:\t" << index << "\n\n";
    }
}

[patrickweiss52]

@MiiNiPaa: ty! I appreciate your help so much!

[patrickweiss52]

@MiiNiPaa: so the code works for strings like hello world, searching for world(it returns the correct index=6) but it doesn't correctly do strings like programming, searching for mm (it returns 9 when it should return 6.)

[MiiNiPaa]

Your code has a bug which prevents finding substring not at the end of original string.

Look at the changes I made (first four lines in my function) and think, why were they neded. Additionally think, why your code does not capture it.