What am I missing in my function?

Hello,
I just wrote another function for checking to see if one string contains another string or not. I named it containsStr(), and I used different logic in it then my last version for a function which does this. But I can't figure out why it doesn't work. Please look over the code, and offer any insight you can (whilst taking care not to comment on the stuff about fingers... :p Sorry, I was bored, and wanted to make my code a little more interesting).

Here's the codepad code link:

C++ code - 75 lines - codepad

Quote:

---

Originally Posted by Programmer_P

Hello,
I just wrote another function for checking to see if one string contains another string or not. I named it containsStr(), and I used different logic in it then my last version for a function which does this. But I can't figure out why it doesn't work. Please look over the code, and offer any insight you can (whilst taking care not to comment on the stuff about fingers... :p Sorry, I was bored, and wanted to make my code a little more interesting).

Here's the codepad code link:

C++ code - 75 lines - codepad

---

why don't just use the member function "find" of string?

Code:

---

string::size_type idx = source_str.find( search_str );

---

I think he's just trying to implement something like strstr() on his own. The find() method is for people who aren't interested in reinventing wheels.

One of the only ways to screw up the naive search string algorithm is by not comparing the subsequent whatever length characters after you've found the initial one in the sourceStr. He needs to look harder at the code that does that. One of the i's is probably not being updated fast enough.

Quote:

---

Originally Posted by Programmer_P

Hello,
I just wrote another function for checking to see if one string contains another string or not. I named it containsStr(), and I used different logic in it then my last version for a function which does this. But I can't figure out why it doesn't work. Please look over the code, and offer any insight you can (whilst taking care not to comment on the stuff about fingers... :p Sorry, I was bored, and wanted to make my code a little more interesting).

Here's the codepad code link:

C++ code - 75 lines - codepad

---

in line 42 put
++i
instead
i+1

Quote:

---

Originally Posted by nimitzhunter

why don't just use the member function "find" of string?

Code:

---

string::size_type idx = source_str.find( search_str );

---

---

Because by the time I had thought of using it, I had already written a version of containsStr() that I was sure would work, and I didn't want to throw the code away, and admit failure. :)

But, alas...
C++ code - 37 lines - codepad

I'm still open for input on the other version though. I still don't know what was wrong with it.

Quote:

---

Originally Posted by Cobs

in line 42 put
++i
instead
i+1

---

Line 42 doesn't increment i, but I went ahead anyway, and changed both increments of i (i.e. the one in the for loop updater, and the other one in the inner for loop block) to pre-incrementing versions instead of post-incrementing versions, but it still doesn't work:

C++ code - 79 lines - codepad

Did I not just explain it?

The naive search string algorithm works as follows: find the initial character of searchstr in sourcestr called position x, with an offset of 0. Compare the next searchstr characters starting at x. Now you either find it or find the next x, by searching for the next occurrence of the initial character of searchstr, at an offset of x+1, and so forth. If you cannot find an occurrence of searchstr[0] in sourcestr, you have a failed search result.

There are only so many ways to screw it up and you screwed up the "Compare the next searchstr characters starting at x," part.

Quote:

---

Originally Posted by whiteflags

Did I not just explain it?

The naive search string algorithm works as follows: find the initial character of searchstr in sourcestr called position x, with an offset of 0. Compare the next searchstr characters starting at x. Now you either find it or find the next x, by searching for the next occurrence of the initial character of searchstr, at an offset of 1, and so forth. If you cannot find an occurrence of searchstr[0] in sourcestr, you have a failed search result.

There are only so many ways to screw it up and you screwed up the "Compare the next searchstr characters starting at x," part.

---

Huh? I'm sorry, but that doesn't make much sense to me...
Are you saying that that's how the "naive" search string algorithm is supposed to work, or are you saying that that's what my code does? Because it seems like to me, that both are false. :) What my code does is it searches for the first character of searchStr in sourceStr, and if it finds it, it then iterates through both strings (starting with the next character up from what was already compared, i.e. the first character of searchStr and the current character of sourceStr), comparing each character. If it finds one that's not a match, it breaks from the inner for loop, after first setting a bool variable called "just_broke" as true. An if statement after the inner for loop then checks to see if just_broke is true or not. If it is not, then we know that it found the entire searchStr in the sourceStr, therefore we return true right away. If it is, then we continue iterating through sourceStr, looking for the first character of searchStr, and go through the whole process again if we find another match. That is basically the logic behind my code, though it does a few other things too.

I honestly cannot make heads or tails of what you just said, in relation to my code, for it sounds like you're saying I should be searching for multiple characters sequentially (i.e. one right after the other) in sourceStr that match the first character of searchStr. :)

Quote:

---

Originally Posted by Programmer_P

Huh? I'm sorry, but that doesn't make much sense to me...
Are you saying that that's how the "naive" search string algorithm is supposed to work, or are you saying that that's what my code does? Because it seems like to me, that both are false. :) What my code does is it searches for the first character of searchStr in sourceStr, and if it finds it, it then iterates through both strings (starting with the next character up from what was already compared, i.e. the first character of searchStr and the current character of sourceStr), comparing each character. If it finds one that's not a match, it breaks from the inner for loop, after first setting a bool variable called "just_broke" as true. An if statement after the inner for loop then checks to see if just_broke is true or not. If it is not, then we know that it found the entire searchStr in the sourceStr, therefore we return true right away. If it is, then we continue iterating through sourceStr, looking for the first character of searchStr, and go through the whole process again if we find another match. That is basically the logic behind my code, though it does a few other things too.

I honestly cannot make heads or tails of what you just said, in relation to my code, for it sounds like you're saying I should be searching for multiple characters sequentially (i.e. one right after the other) in sourceStr that match the first character of searchStr. :)

---

Go to your function and print out whatever being compared. It would help to see what's going on.

I will just further state that if you implement what I've posted, it will work. I don't care what you've done or what you think you've done, (I never do,) I'm only assuming that what I explained is what you mean to do, because it works.

Quote:

---

Originally Posted by nimitzhunter

Go to your function and print out whatever being compared. It would help to see what's going on.

---

Done.

C++ code - 97 lines - codepad

OK maybe I do need to explain again. You have to find the initial character of the keyword so you know where to look for the rest of the keyword. If you find said character, you should do a regular comparison involving the next keyword.length() characters in the source string, because that could be the substring inside the source string you want. If you didn't find the keyword, the next logical place to start the next comparison is at the next occurrence of keyword[0]. By this, I mean if that a previous occurrence of keyword[0] is at x, the very next place you can start looking again for keyword[0] is x+1. You just keep going until you find the word, or stop finding keyword[0] (in the case of a failed search).

Quote:

---

Originally Posted by whiteflags

OK maybe I do need to explain again. You have to find the initial character of the keyword so you know where to look for the rest of the keyword. If you find said character, you should do a regular comparison involving the next keyword.length() characters in the source string, because that could be the substring inside the source string you want. If you didn't find the keyword, the next logical place to start the next comparison is at the next occurrence of keyword[0]. By this, I mean if that a previous occurrence of keyword[0] is at x, the very next place you can start looking again for keyword[0] is x+1. You just keep going until you find the word, or stop finding keyword[0] (in the case of a failed search).

---

Right. I know that.
That is the reason why my code is supposed to do exactly that...

And yet it does not, for the rather obvious reason I pointed out several times. You are not comparing much of anything after you find the initial character of the keyword.

It makes more sense if you break it up:

Code:

---

#include <string>
#include <iostream>
using std::cout;
using std::string;
bool contains(const string &haystack, const string &needle)
{
    if (needle[0] != '\0') {
        for(string::size_type i = 0; (i = haystack.find(needle[0], i)) != string::npos; ++i) {
            if (haystack.compare(i, needle.size(), needle) == 0)
                return true;
        }
    }
    return false;
}

---

You can reimplement all of those functions if you want. Or you can reimplement all of the steps as one function if you want. And you want to make sure that you compare all of the search string.

So:
1) Because you have, for bad reasons, tried to split your check-the-rest-of-the-substring up into two pieces, you check [0] against [0], [1] against [1], and then ... [2] against [1], rather than [2] against [2].
2) Since you are fiddling with i in your check-the-rest-of-the-substring part, you completely destroy the ability of your outer for loop to go through the string. Don't do that. Your check-the-rest-of-the-substring part only needs a single auxiliary variable, which will serve as the offset in both the source string and the search string. (Offset from [i] in the one case, and from [0] in the other.)