What am I missing in my function?

This is a discussion on What am I missing in my function? within the C++ Programming forums, part of the General Programming Boards category; Hello, I just wrote another function for checking to see if one string contains another string or not. I named ...

  1. #1
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827

    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... 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
    Last edited by Programmer_P; 01-13-2011 at 09:03 PM.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  2. #2
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    455
    Quote Originally Posted by Programmer_P View Post
    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... 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 );
    "All that we see or seem
    Is but a dream within a dream." - Poe

  3. #3
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,709
    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.

  4. #4
    Registered User
    Join Date
    Jan 2011
    Posts
    7
    Quote Originally Posted by Programmer_P View Post
    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... 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

  5. #5
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Quote Originally Posted by nimitzhunter View Post
    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.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  6. #6
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Quote Originally Posted by Cobs View Post
    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
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  7. #7
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,709
    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.
    Last edited by whiteflags; 01-13-2011 at 09:22 PM.

  8. #8
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Quote Originally Posted by whiteflags View Post
    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.
    Last edited by Programmer_P; 01-13-2011 at 09:34 PM.
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  9. #9
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    455
    Quote Originally Posted by Programmer_P View Post
    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.
    "All that we see or seem
    Is but a dream within a dream." - Poe

  10. #10
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,709
    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.

  11. #11
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Quote Originally Posted by nimitzhunter View Post
    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
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  12. #12
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,709
    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).

  13. #13
    Programming Ninja In-T...
    Join Date
    May 2009
    Posts
    827
    Quote Originally Posted by whiteflags View Post
    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...
    I'm an alien from another world. Planet Earth is only my vacation home, and I'm not liking it.

  14. #14
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,709
    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.

  15. #15
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.)

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Compiling Libraries in C
    By TheOriginalGame in forum C Programming
    Replies: 3
    Last Post: 08-15-2010, 11:19 AM
  2. <Gulp>
    By kryptkat in forum Windows Programming
    Replies: 7
    Last Post: 01-14-2006, 12:03 PM
  3. Problem with Visual C++ Object-Oriented Programming Book.
    By GameGenie in forum C++ Programming
    Replies: 9
    Last Post: 08-29-2005, 11:21 PM
  4. ras.h errors
    By Trent_Easton in forum Windows Programming
    Replies: 8
    Last Post: 07-15-2005, 10:52 PM
  5. c++ linking problem for x11
    By kron in forum Linux Programming
    Replies: 1
    Last Post: 11-19-2004, 09:18 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21